一、题目

二、思路

（1）确定状态

d p [ i ] dp[i]dp[i]表示nums中以nums[i]结尾子数组的最大子序和。

（2）状态转移方程（描述子问题之间的联系）

假设数组nums[i]值全部严格大于0，则一定有：

但是dp[i-1]可能是负数的，分类讨论：

如果dp[i-1]大于0，可以把nums[i]直接接在dp[i-1]表示的那个数组后面，构成当前最大连续子数组和dp[i]，注意这里nums[i]可能大于0（加上去当然没问题），虽然也可能nums[i]小于0，也得加到dp[i-1]上，因为我们已经定义好了d p [ i ] dp[i]dp[i]表示nums中以nums[i]结尾子数组的最大子序和。；

如果dp[i-1]小于等于0，则nums[i]加在dp[i-1]上后并不会得到最大子序和，所以需要对当前的dp[i]另起炉灶，此时单独的nums[i]就是dp[i]，但是注意这个dp[i]不一定是从开始到现在过程中的最大子序列和。

（3）边界条件 + 初始情况

只有第一个数字时：dp[0] = nums[0]。

（4）计算顺序

从左往右，从下标0开始遍历。

三、 代码

class Solution {
public:
    int maxSubArray(vector<int>& nums) {
        int n = nums.size();
        vector<int>dp(n, 0);
        int ans = nums[0];
        dp[0] = nums[0];
        for(int i = 1; i < n; i++){
            dp[i] = max(dp[i-1] + nums[i], nums[i]);
            ans = max(ans, dp[i]);
        }
        return ans;
    }
};