视频讲解：https://www.bilibili.com/video/BV19V4y1F7b5

https://programmercarl.com/0053.%E6%9C%80%E5%A4%A7%E5%AD%90%E5%BA%8F%E5%92%8C%EF%BC%88%E5%8A%A8%E6%80%81%E8%A7%84%E5%88%92%EF%BC%89.html

1.本题的贪心算法在之前已经完成，今天又回顾了一下贪心算法，相较于使用贪心算法，本题使用动态规划的思路似乎更容易理解一下，定义dp数组dp[i] 以i为结尾的最大和的值，找到可以用于状态转移的两个状态。一个就是接着前面的数接着相加，另一个就是以当前的数为开头接着计算，有一种刚才那个最大和的号玩废了，换了个小号。

CPP

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