連續子陣列的最大和

問題描述:求下標 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;
    }