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

dp[i]代表以array[i]为结尾的序列的最大和，dp[0] = array[0]; dp[i+1] = dp[i] > 0? dp[i] + array[i+1] : array[i+1]。

可以只用一个变量代替数组，即sum = 0; sum = sum > 0 ? sum + array[i] : array[i]，过程中记录sum的最大值。

class Solution {
public:
    int FindGreatestSumOfSubArray(vector<int> array) {
        int ans = 0x80000000, sum = 0, len = array.size();
        for (int i = 0; i < len; ++i){
            if (sum <= 0) sum = array[i];
            else sum += array[i];
            if (sum > ans) ans = sum;
        }
        return ans;
    }
};