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

• 动态规划，定义dp数组记录当前子数组最大和；
• 区间左端点更新条件：前一子数组最大和小于0；
• 区间更新条件：当前子数组最大和更新和当前子数组最大和不变但区间增大；
• 将区间范围内的数组元素放入结果。

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