连续子数组的最大和

问题描述:求下标 0-n 的连续子数组的最大和

假设数组下标:$0...i...j...n$ 区间$[i,j]$是最大和 maxsum

maxsum有2种情况

1.假设 maxsum<= 0; 只有一种情况，所有数都为非正数. 如果 $a[x]>0$,那么假设不成立。

maxsum = max(maxsum,a[x]);(即找最大的非正数)

2.假设 maxsum>0;那么

a[x] <= maxsum; 并且 a[i] >= 0, a[j] >= 0;(如果a[i]<0,那么不选i,能让maxsum变大,与假设矛盾)

最大和为 从非负数开始 到非负数结束

阻止区间向两边扩展的条件。 1.到头了。(即到达左右边界,没有元素了) 2.左边。从$i-1+i-2+...+k<0,(0\le k\le i-1)$.(从i-1开始，向左累加，找不到非负数和了). 右边。从$j+1+j+2+...+n<0,$.(从j+1开始，向右累加，找不到非负数和了).

我们从左到右遍历，那么左边利用无法扩展(第2条)，右边利用到头了。

如何确定区间 [i,j]

假设我们找到 一个正数, 下标 m，设 T = $n-1+n-2+...+m$ 1.右边 是正数，那么累加。 (T > 0) 2.右边 是非负数, 假设下标 n

1.如果 T < 0,这一块已经无法扩展了，必须重新寻找下一个区间。 2.T == 0, 加和没加一样了 3.如果 T > 0, 是否存在 m<s<n, 使得 $a_s+...+a_n>a_m+...+a_s+...+a_n$ 假设条件成立,那么 $a_m+...+a_{s-1}<0$,这是不存在的, 处理第一条时，已经处理完毕。

也就是说 从一个正数开始 , 当 和 大于0 时,最大和在 当前区间内(正数下标开头)或者 不在当前区间， 不会出现 最大和的开始下标, 出现在 当前区间中间的部分。

代码：

int maxSubArray(vector<int>& nums) { static auto speedup = [](){ios::sync_with_stdio(false);cin.tie(nullptr);return nullptr;}(); if(nums.size() == 0) return 0; int sum = 0,res = INT_MIN; for(int i = 0;i<nums.size();++i){ sum+= nums[i]; res = max(sum,res); //sum 就是 T,利用sum = 0,代替 重新寻找区间 if(sum<0){ sum = 0; } } return res; }