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

class Solution {
public:
    int FindGreatestSumOfSubArray(vector<int> array) {
        int len = array.size();
        vector<int> dp;
        int max = array[0];
        dp.push_back(array[0]);
        for(int i=1; i < len; i++){
            int newMax = dp[i-1] + array[i];
            if(newMax > array[i]) dp.push_back(newMax);
            else dp.push_back(array[i]);
            if(dp[i] > max) max = dp[i];
        }
        return max;
    }

};

动态规划一般比较烧脑。最主要的是找出一个递推方程： 对于当前某个值，思考把它串在前续上更大，还是断开单独起更大。 那么自然而然就需要维护一个到当前位置的前一个位置为止，连续串的最大和数组。 其实困扰人的关键问题在于里面有可能夹杂负数，那么负数在断开还是串进去，其实取决于不看负数本身，而是看串上负数之后，是否还有剩余价值（>0）. 上面这个算法还可以继续优化，使得空间复杂度为 O(1), 即之间把 dp[] 写在原数组里。