题目描述

blablabla

算法1

1. dp[i] 表示以nums[i]结尾的连续后缀和的最大值
2. 根据dp[i - 1] >= 0 或者dp[i - 1] < 0 将集合划分

C++ 代码

class Solution {
public:
    int maxSubArray(vector<int>& nums) {
        int n = nums.size();
        vector<int> dp(n);
        dp[0] = nums[0];
        int res = dp[0];
        for(int i = 1; i < nums.size(); i++){
        //dp[i - 1] >= 0时，以nums[i]结尾的连续后缀和的最大值就是dp[i - 1] + nums[i]
            if(dp[i - 1] >= 0) dp[i] = dp[i - 1] + nums[i];
        //dp[i - 1] < 0 时，以nums[i]结尾的连续后缀和的最大值就是nums[i]
            else dp[i] = nums[i];
            res = max(dp[i], res);
        }
        return res;
    }
};