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

• 动态规划，dp数组存储前一最大和、当前最大和；
• 左区间端点更新条件：前一最大和小于0；
• 区间端点更新条件：当前最大和更新，或者当前最大和不变但区间范围增大；
• 遍历完成后，返回区间内的数组元素。

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