题解 | #连续子数组的最大和(二)#

class Solution {
public:
    vector<int> FindGreatestSumOfSubArray(vector<int>& array) {
        int max=-100,sum=0; 
        vector<int> res; 
        int left=0,right,oldleft,oldright;
        for(int i=0;i<array.size();i++){          //sum每次与当前值相加
            sum += array[i];
            if(sum >= max){
                max = sum; 
                right = i;
            }         //只要出现最大值，就赋值给max
            if(sum < 0){
                sum = 0;
                oldleft = left;    //记录下来当前的前后，如果后面全负也能记录下来
                oldright = right;
                left = i + 1;
            }      //如果sum<0证明前面这一部分已经对最大值无意义，更新sum
        }
        if(left > right){   //说明后面是全负，用旧的
            for(int i = oldleft;i <= oldright;i++){
                res.push_back(array[i]);
            }
        }
        else{
            for(int i = left;i <= right;i++){
                res.push_back(array[i]);
            }
        }
        if(res.size() == 0){  //说明全负，找出一个最大值输出
            int maxl=-100;
            for(auto &x : array){
                if(x>maxl) maxl=x;
            }
            res.push_back(maxl);
        }
        return res;
    }
};