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

时间复杂度O(N), 空间复杂度O(N)。可以发现，状态转移方程中，dp[i]仅与dp[i-1]有关，所以我们可以利用滚动数组的思想进行简化达到O(1)的空间复杂度。

「C++ 代码」

class Solution {
public:
    /**
     * 代码中的类名、方法名、参数名已经指定，请勿修改，直接返回方法规定的值即可
     *
     * 
     * @param array int整型vector 
     * @return int整型vector
     */
    vector<int> FindGreatestSumOfSubArray(vector<int>& array) {
        int n = array.size();
        // dp[i]记录的是以array[i]为结尾的连续子数组最大和
        vector<int> dp(n);
        // 初始状态：第一个元素以自身为结束元素是最大和
        dp[0] = array[0];
        // max_sum记录目前最大的连续子数组和
        int max_sum = dp[0];
        // left指示目前计算的连续子数组和的左边界
        int left = 0;
        // start和end指示目前最大和的连续子数组的左右边界
        int start = 0, end = 0;
        for(int i=1; i<n; ++i){
            // 计算以当前元素结尾的连续子数组最大和
            dp[i] = max(array[i], dp[i-1]+array[i]);
            // 如果是以当前元素为单元素，则后续计算的最大和连续子数组都以该元素为左边界
            if(dp[i] > (dp[i-1]+array[i])){
                // 更新left指示的位置
                left = i;
            }
            // 如果当前计算的连续子数组和是最大的，或者说，并列第一但长度更大，那么我们更新max_sum以及左右边界start和end
            if(dp[i] > max_sum || (dp[i]==max_sum && (i-left)>(end-start))){
                end = i;
                start = left;
                max_sum = dp[i];
            }
        }
        // 依据计算的最大和连续子数组的左右边界start和end记录我们的答案
        vector<int> res;
        for(int i=start; i<=end; ++i){
            res.emplace_back(array[i]);
        }
        return res;
    }
};