Find the contiguous subarray within an array (containing at least one number) which has the largest sum.
For example, given the array [−2,1,−3,4,−1,2,1,−5,4],
the contiguous subarray [4,−1,2,1] has the largest sum = 6.
If you have figured out the O(n) solution, try coding another solution using the divide and conquer approach, which is more subtle.
1 public class Solution { 2 public int maxSubArray(int[] A) { 3 int sum=0; 4 int max=Integer.MIN_VALUE; 5 for(int i=0;i<A.length;++i){ 6 sum+=A[i]; 7 if(sum>=max) 8 max=sum; 9 if(sum<0) 10 sum=0; 11 } 12 return max; 13 } 14 }
原文：http://www.cnblogs.com/Phoebe815/p/4048559.html