[Leetcode] maximun subarray 最大子数组

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.

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

思路：这题和jump game、jump game ii 类似。定义两个变量，一个维护目前的最大值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<n;++i)
 8         {
 9             sum+=A[i];
10             maxValue=max(maxValue,sum);
11             if(sum<0)   
12                 sum=0;
13         }    
14         return maxValue;
15     }
16 };

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

代码如下：

 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 };

[Leetcode] maximun subarray 最大子数组

推荐阅读