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

class Solution {
public:
    /**
     * 代码中的类名、方法名、参数名已经指定，请勿修改，直接返回方法规定的值即可
     *
     * 
     * @param array int整型vector 
     * @return int整型vector
     */
    vector<int> FindGreatestSumOfSubArray(vector<int>& array) {
        vector<int> res;
        vector<int> dp(array.size(), 0);
        if(array.size()==0) return res;
        int l=0, r=0;
        int ll=0, rr=0;
        int maxval=array[0];
        dp[0] = array[0];
        for(int i=1; i<array.size(); i++)
        {
            r++;
            if(dp[i-1]+array[i]<array[i])
            {
                dp[i] = array[i];
                l=r;
            }
            else if(dp[i-1]+array[i]>=array[i])
            {
                dp[i] = dp[i-1]+array[i];
            }
            if(dp[i]>=maxval)
            {
                ll = l;
                rr = r;
                maxval = dp[i];
            }

        }
        for(int i=ll; i<=rr; i++)
        {
            res.push_back(array[i]);
        }
        return res;
    }
};