連續子陣列的最大和

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