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

class Solution {
public:
    vector<int> FindGreatestSumOfSubArray(vector<int>& array) {
        // write code here
        // 用start end 记录下最长子数组的起始和结束
        // 用 maxLen 记录最大长度
        vector<int> res;
        if(array.size() == 0)    return res;
        int start = 0, i = -1, end = 0, maxLen = INT_MIN, maxSum = INT_MIN, curSum = 0;
        for(int k = 0; k < array.size(); k++) {
            curSum += array[k];
            if(curSum > maxSum || (curSum == maxSum && k - i >= maxLen)) {
                // 注意更新条件！
                start = i + 1;
                end = k;
                maxSum = curSum;
                maxLen = k - i;
            }                      
            if(curSum < 0) {
                curSum = 0;
                i = k;                
            }
        }
        for(int k = start; k <= end; k++) {
            res.push_back(array[k]);
        }
        return res;
    }
};