一、题目

二、思路

（1）确定状态
$dp[i]$表示nums中以nums[i]结尾的最大子序和。

（2）状态转移方程（描述子问题之间的联系）
假设数组nums[i]值全部严格大于0，则一定有：$$dp[i]=max(dp[i-1]+nums[i],nums[i])$$
但是dp[i-1]可能是负数的，分类讨论：

• 如果dp[i-1]大于0，可以把nums[i]直接接在dp[i-1]表示的那个数组后面，构成当前最大连续子数组和dp[i]；
• 如果dp[i-1]小于等于0，则nums[i]加在dp[i-1]上后并不会得到最大子序和，所以需要对当前的dp[i]另起炉灶，此时单独的nums[i]就是dp[i]，但是注意这个dp[i]不一定是从开始到现在过程中的最大子序列和。 d p [ i ] = { d p [ i − 1 ] + n u m s [ i ] ,  if  d p [ i − 1 ] > 0  nums  [ i ] ,  if  d p [ i − 1 ] ≤ 0 d p[i]=\left\{
  dp[i−1]+nums[i], nums [i], if  if dp[i−1]>0dp[i−1]≤0 $$\begin{array}{lll}dp[i-1]+nums[i],& \text{ if }& dp[i-1]>0\\ \text{ nums }[i],& \text{ if }& dp[i-1]\le 0\end{array}$$
  \right. dp[i]={dp[i−1]+nums[i], nums [i],​ if  if ​dp[i−1]>0dp[i−1]≤0​写成max的形式就不用分类讨论了：$$dp[i]=\max \{nums[i],dp[i-1]+nums[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;
    }
};

  

 

  
1
  
2
  
3
  
4
  
5
  
6
  
7
  
8
  
9
  
10
  
11
  
12
  
13
  
14
 

文章来源: andyguo.blog.csdn.net，作者：山顶夕景，版权归原作者所有，如需转载，请联系作者。

原文链接：andyguo.blog.csdn.net/article/details/123289678