1 思考

• 核心是看到 局部和 怎么更新的， 这样对于即使是负数的各种数组值都能兼容，
• 算法尽量简单，没有过渡使用 max
• 延展取得相关和序列的方法，我放在注释里面，有空再尝试
• 【2021.1】依然没有消化，看了4年前的实现 找到一些思路

2 code

class Solution {
public:
    int FindGreatestSumOfSubArray(vector<int> array) {
    //最难的就是局部和的使用，复杂度还是O(N)
        //(array == nullptr ,畅度>=1
        if(0 == array.size() ){
            return 0;//exception
        }
        int localSum =0 ,globalSum = INT32_MIN;//0x8000000
        //only iterate 1
        for(int i =0 ;i < array.size() ; i++){
            
            if(localSum <0){
                //update new one, 家里没粮 就新开炉灶
                localSum = array[i];
                //localStart  and localEnd 都更新
            }else{
                localSum +=array[i];
                //localEnd update
            }
            
            if(localSum > globalSum){
                globalSum = localSum;
                //gloabalStart 
                //globalEnd
            }
            
        }
        return globalSum;
    }
};