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.

More practice:

If you have figured out the O(n) solution, try coding another solution using the divide and conquer approach, which is more subtle.

题意：给定由正负整数组成的数组，问和最大的子数组，返回和。

思路：这题和 、  类似。定义两个变量，一个维护目前的最大值maxValue，一个是之前元素值的最大值sum，当sum小于0时说明，若算上之前的数会是整体的最大值减小，所以舍弃。时间复杂度为O(n)。代码如下：

1 class Solution { 2 public: 3     int maxSubArray(int A[], int n)  4     { 5         if(n==0)    return 0; 6         int sum=0,maxValue=A[0]; 7         for(int i=0;i

方法二：分治。参考的博客。分治的思想类似二分搜索，首先将数组一分为二，分别找出左边和右边的最大子数组之和，然后从中间开始向左右分别扫描，求出的最大值分别和左右两边得到的最大值相比较，取最大值。

代码如下：

1 class Solution { 2 public: 3     int maxSubArray(int A[], int n)  4     { 5         if(n==0)    return 0; 6         return helper(A,0,n-1); 7     } 8  9     int helper(int A[],int left,int right)10     {11         if(left>=right) return A[left];12         int mid=(left+right)>>1;13         int lmx=helper(A,left,mid-1);14         int rmx=helper(A,mid+1,right);15 16         int mMax=A[mid],temp=mMax;17 18         //遍历左半端，19         for(int i=mid-1;i>=left;--i)20         {21             temp+=A[i];22             mMax=max(mMax,temp);23         }24         temp=mMax;  //向右25         for(int i=mid+1;i<=right;++i)26         {27             temp+=A[i];28             mMax=max(mMax,temp);29         }30 31         return max(mMax,max(lmx,rmx));32     }33 };