给定一个整数数组 nums ，找到一个具有最大和的连续子数组（子数组最少包含一个元素），返回其最大和。
示例:
输入: [-2,1,-3,4,-1,2,1,-5,4],
输出: 6
解释: 连续子数组 [4,-1,2,1] 的和最大，为 6。
进阶:
如果你已经实现复杂度为 O(n) 的解法，尝试使用更为精妙的分治法求解。
递归法求解：一个最大的子序和，我们从中间将这个序列分开，那么这个最大值有三种可能，这个最大值出现在左半边，或者出现在右半边，或者横跨中间。因此我们根据这个思想，在这个三个当中求解出最大值就可以了，同理对于左半边和右半边的最大值我们也是这么求解的。
class Solution {
public:
int maxsum(int l,int r,vector<int>& nums)
{
int ans;
if(r==l)
return nums[l];
int mid=(l+r)/2;
ans=max(maxsum(l,mid,nums),maxsum(mid+1,r,nums));
int templ=nums[mid],t=0;
for(int i=mid;i>=l;i--)
templ=max(templ,t+=nums[i]);
int tempr=nums[mid+1];t=0;
for(int i=mid+1;i<=r;i++)
tempr=max(tempr,t+=nums[i]);
return max(ans,templ+tempr);
}
int maxSubArray(vector<int>& nums) {
int si=nums.size();
if(si==0)
return 0;
return maxsum(0,si-1,nums);
}
};
O(n)解法：定义一个数组dp，存储截止到元素 i 的最大和值。
class Solution {
public:
int maxSubArray(vector<int>& nums) {
int si=nums.size();
if(si==0)
return 0;
int dp[si];
int ans=nums[0];dp[0]=nums[0];
for(int i=1;i<si;i++)
{
dp[i]=nums[i]+(dp[i-1]>0?dp[i-1]:0);
ans=max(ans,dp[i]);
}
return ans;
}
};