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

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

maxsum有2种情况

1.假设 maxsum<= 0; 只有一种情况，所有数都为非正数. 如果 a [ x ] > 0 a[x] >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 ≤ k ≤ i − 1 ) i-1+i-2+...+k <0,(0 \leq k \leq i-1) i−1+i−2+...+k<0,(0≤k≤i−1).(从i-1开始，向左累加，找不到非负数和了).
右边。从 j + 1 + j + 2 + . . . + n < 0 , j+1+j+2+...+n <0, j+1+j+2+...+n<0,.(从j+1开始，向右累加，找不到非负数和了).

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

如何确定区间 [i,j]

假设我们找到 一个正数, 下标 m，设 T = n − 1 + n − 2 + . . . + m n-1+n-2+...+m 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_s+...+a_n > a_m + ...+a_s + ...+ a_n as​+...+an​>am​+...+as​+...+an​
假设条件成立,那么
a m + . . . + a s − 1 < 0 a_m + ... + a_{s-1} < 0 am​+...+as−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;
    }