1.题目

2.思路

（1）确定状态
状态为$dp[i]$，表示以$nums[i]$为末尾的连续序列的最大和，$nums[i]$必须作为连续序列的末尾。

（2）状态转移方程
1）这个最大和的连续序列只有一个元素时，即以nums【i】开始，以nums【i】结尾，即最大和为nums【i】。
2）若有多个元素，即从前面某处nums【p】开始（p小于i），一直到nums【i】结尾，即最大和为$dp[i-1]+nums[i]$。
所以转移方程为$dp[i]=max\{nums[i]+dp[i-1],nums[i]\}$

（3）初始条件+边界情况
边界为$dp[0]=A[0]$

（4）计算顺序
因为计算dp【i】需要用到dp[i-1]的内容，所以遍历顺序为i从小到大枚举。

3.代码

class Solution {
public:
    int maxSubArray(vector<int>& nums) {
        int n=nums.size();
        int dp[n];
        //边界
        dp[0]=nums[0];
        
        for(int i=1;i<nums.size();i++){
            dp[i]=max(dp[i-1]+nums[i],nums[i]);
        }
        //dp[i]存放以A[i]为结尾的连续序列的最大和，需要遍历i得到最大的才是结果
        int k=0;
        for(int i=1;i<n;i++){
            if(dp[i]>dp[k]){
                k=i;
            }
        }
        return dp[k];
    }
};

  

 

  
1
  
2
  
3
  
4
  
5
  
6
  
7
  
8
  
9
  
10
  
11
  
12
  
13
  
14
  
15
  
16
  
17
  
18
  
19
  
20
  
21
 

4.类似题

LeetCode上其他类似的背包问题：
0-1 背包问题
　　第 416 题：分割等和子集；
　　第 474 题：一和零；
　　第 494 题：目标和。
　　 组合总和IV

完全背包问题如下：
　　第 322 题：零钱兑换；
　　第 518 题：零钱兑换 II

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

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