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

class Solution {
public:
    int FindGreatestSumOfSubArray(vector<int> array) {
        int size = array.size();
        vector<int> dp(size);
        dp[0] = array[0];
        int ans=array[0];
        for(int i=0; i<size-1; i++){
             //1. 假设dp[i]表示以array[i]结尾的子数组中最大的和
             //2. 则dp[i+1]等于dp[i]加上当前的数，即dp[i]+array[i+1]
          	 //3. 如果dp[i]是负数，则无论array[i+1]是正还是负数，dp[i+1]都会变小，
             //   那应该不要dp[i], 即dp[i+1] = array[i+1]
            dp[i+1] = array[i+1]+(dp[i]<0?0:dp[i]);
            ans = dp[i+1]>ans?dp[i+1]:ans;
        }
        return ans;
    }
};