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.
click to show more practice.
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)。代码如下：
class Solution {
public:
int maxSubArray(int A[], int n)
{
if(n==) return ;
int sum=,maxValue=A[];
for(int i=;i<n;++i)
{
sum+=A[i];
maxValue=max(maxValue,sum);
if(sum<)
sum=;
}
return maxValue;
}
};
方法二：分治。参考Grandyang的博客。分治的思想类似二分搜索，首先将数组一分为二，分别找出左边和右边的最大子数组之和，然后从中间开始向左右分别扫描，求出的最大值分别和左右两边得到的最大值相比较，取最大值。
代码如下：
class Solution {
public:
int maxSubArray(int A[], int n)
{
if(n==) return ;
return helper(A,,n-);
}
int helper(int A[],int left,int right)
{
if(left>=right) return A[left];
int mid=(left+right)>>;
int lmx=helper(A,left,mid-);
int rmx=helper(A,mid+,right);
int mMax=A[mid],temp=mMax;
//遍历左半端，
for(int i=mid-;i>=left;--i)
{
temp+=A[i];
mMax=max(mMax,temp);
}
temp=mMax; //向右
for(int i=mid+;i<=right;++i)
{
temp+=A[i];
mMax=max(mMax,temp);
}
return max(mMax,max(lmx,rmx));
}
};
