如图所示
下面是抄的。。。实在没想出来
题目描述： 最大子序和
给定一个序列（至少含有 1 个数），从该序列中寻找一个连续的子序列，使得子序列的和最大。
例如，给定序列 [-2,1,-3,4,-1,2,1,-5,4]，
连续子序列 [4,-1,2,1] 的和最大，为 6。
扩展练习:
若你已实现复杂度为 O(n) 的解法，尝试使用更为精妙的分治法求解。
解题思路一：动态规划
求和，然后判断和是否小于0，因为只要前面的和小于0，那么后面的数加上前面的和就一定比自身小，所以又重新求和，并和之前的最大子序和比较，取最大值。
代码：
class Solution {
public:
int maxSubArray(vector<int>& nums) {
int ans = 0, maxn = INT_MIN;
int len = nums.size();
for(int i = 0; i < len; i++){
if(ans < 0) ans = 0; //如果前面的和小0，那么重新开始求和
ans += nums[i];
maxn = max(maxn, ans);
}
return maxn;
}
};
解题思路二：分治
刚开始觉得左右递归后，中间还有可能的答案，但是又不知道中间的部分怎么办；看了别人的代码后发现把中间的最大子序和也一起递归就行了。
代码：
class Solution {
public:
int maxSubArray(vector<int>& nums) {
return divide(nums, 0, nums.size()-1);
}
int divide(vector<int>& nums, int l, int r) {
if(l == r) return nums[l];
if(l == r-1) return max(nums[l], max(nums[r], nums[l]+nums[r]));
int mid = (l+r)>>1;
int lret = divide(nums, l, mid-1);
int rret = divide(nums, mid+1, r);
int mret = nums[mid];
int sum = mret;
for(int i = mid-1; i >= l ; i --) {
sum += nums[i];
// if(sum < 0) sum = 0;
mret = max(mret, sum);
}
sum = mret; //保存已经计算过的左边的最大子序和
for(int i = mid+1; i <= r ; i ++) {
sum += nums[i];
// if(sum < 0) sum = 0;
mret = max(mret, sum);
}
return max(lret, max(rret, mret));
}
};
解题思路三：暴力法（复杂度太高被T了）
代码：
class Solution {
public:
int maxSubArray(vector<int>& nums) {
int ans, ma, sum;
int len=nums.size();
ans = nums[0];
for(int i = 0 ; i < len ; i ++) {
ma = ans;
sum = 0;
for(int j = i ; j < len ; j ++) {
sum += nums[j];
ma = max(ma, sum);
ans = max(ans, ma);
}
}
return ans;
}
};
作者：江江蒋
来源：CSDN
原文：https://blog.csdn.net/qq_33168253/article/details/79775107
版权声明：本文为博主原创文章，转载请附上博文链接！
