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

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