leetCode 53.最大子数和 图解 + 贪心算法/动态规划+优化

53. 最大子数组和 - 力扣（LeetCode）

---

给你一个整数数组 nums ，请你找出一个具有最大和的连续子数组（子数组最少包含一个元素），返回其最大和。子数组 是数组中的一个连续部分。

---

示例 1：

输入：nums = [-2,1,-3,4,-1,2,1,-5,4]
输出：6
解释：连续子数组 [4,-1,2,1] 的和最大，为 6 

示例 2：

输入：nums = [1]
输出：1

示例 3：

输入：nums = [5,4,-1,7,8]
输出：23

---

>>思路和分析 

一、贪心解法 贪心贪在哪里(=@__@=)？

我们看示例1，若-2 和 1在一起累加，计算起点一定从1开始，因为负数只会拉低总和，这就是贪心贪的地方！

• 局部最优：当前 “连续和” 为负数的时候立刻放弃，从下一个元素重新计算 “连续和”，因为负数加上下一个元素 “连续和” 只会越来越小。
• 全局最优：选取最大“连续和”

局部最优的情况下，并记录最大的 “连续和” ，可以推出全局最优

不断调整最大子序和区间的起始位置，区间终止位置是不用调整的，因为区间的终止位置，在count取得最大值了，及时记录下来了。这相当于是用result记录最大子序和区间和（变相的算是调整了终止位置） 

if (count > result) result = count;

C++代码：

class Solution {
public:
    int maxSubArray(vector<int>& nums) {
        int result = INT32_MIN;
        int count = 0;
        for (int i = 0; i < nums.size(); i++) {
            count += nums[i];
            if (count > result) { // 取区间累计的最大值（相当于不断确定最大子序终止位置）
                result = count;
            }
            if (count <= 0) count = 0; // 相当于重置最大子序起始位置，因为遇到负数一定是拉低总和
        }
        return result;
    }
};

• 时间复杂度：O(n)
• 空间复杂度：O(1)

---

 二、动态规划 

dp[i] : 表示包括 i 之前的最大连续子序列和

i = 0，dp[0] = -2

i = 1，count = (-2) + 1 = -1,在count 和 nums[1] = 1中选取最大值，即 dp[1] = max(dp[0] + nums[1],nums[1]); 所以dp[1] = 1

i = 2，由于前面已经计算过包括i = 1之前的最大连续子序列和，并且将值保存在 dp[1] 里，所以count = dp[1] + (-3) = 1 + (-3) = -2，接着在count 和 nums[2] = -3中选取最大值，即 dp[2] = max(dp[1] + nums[2],nums[2]);所以dp[2] = -2，表示包括i = 2之前的最大连续子序列和。同理，如下推导

i = 3，count = dp[2] + 4 = 2，dp[3] = max(2,4);所以dp[3] = 4。发现 count < nums[3]，这时候取最大值就可以让dp[3] = nums[3]，表示接下来，可以调整起点，让 i = 3 为起点

i = 4，count = dp[3] + (-1) = 3，dp[4] = max(3,-1);所以dp[4] = 3.发现count > nums[4]的，表示可以保持让 i = 3为起点

i = 5，count = dp[4] + 2 = 5，dp[5] = max(5,2);所以dp[5] = 5.发现count > nums[5]的，表示可以保持让 i = 3为起点

i = 6，count = dp[5] + 1 = 6，dp[6] = max(6,1);所以dp[6] = 6.发现count > nums[6]的，表示可以保持让 i = 3为起点

i = 7，count = dp[6] + (-5) = 1，dp[7] = max(1,-5);所以dp[7]=1.发现count > nums[7]的，表示可以保持让 i = 3为起点

i = 8，count = dp[7] + 4 = 5，dp[8] = max(5,4);所以dp[8] = 5.发现count > nums[8]的，表示可以保持让 i = 3为起点 

① count = dp[i-1] + nums[i];
 
② dp[i] = max(count,nums[i]);
        ↓
        ↓
        ↓
        ↓
③ dp[i] = max(dp[i-1] + nums[i],dp[i]);

---

>>动规五部曲

 1.确定dp数组（dp table）以及下标的含义

• dp[i]:包括下标 i (以nums[i]为结尾)的最大连续子序列和为dp[i]

2.确定递推公式

• 第一种情况，在遍历nums[i]时，延续着前面连续子序列的和（dp[i-1]），
  • 即：dp[i-1] + nums[i];
• 第二种情况，在遍历nums[i]时，不延续前面连续子序列的和（dp[i-1]），从头开始计算，
  • 即：nums[i];

最后，我们取这两种情况的最大值，dp[i] = max(dp[i-1]+nums[i],nums[i]);

3.数组初始化

• 从递推公式可看出dp[i]依赖于dp[i-1]的状态，dp[0]就是递推公式的基础
• dp[0] = nums[0]

4.确定遍历顺序

• 从递推公式可看出dp[i]依赖于dp[i-1]的状态，故需从前往后遍历

5.举例推导dp数组

class Solution {
public:
    int maxSubArray(vector<int>& nums) {
        if (nums.size() == 0) return 0;
        vector<int> dp(nums.size(), 0); // dp[i]表示包括i之前的最大连续子序列和
        dp[0] = nums[0];
        int result = dp[0];
        for (int i = 1; i < nums.size(); i++) {
            dp[i] = max(dp[i - 1] + nums[i], nums[i]); // 状态转移公式
            if (dp[i] > result) result = dp[i]; // result 保存dp[i]的最大值
        }
        return result;
    }
};

• 时间复杂度：O(n)
• 空间复杂度：O(n)

>>优化空间复杂度

class Solution {
public:
    // 动态规划 + 优化空间复杂度
    int maxSubArray(vector<int>& nums) {
        if(nums.size() == 0) return 0;
        int pre = nums[0];
        int result = nums[0];
        for(int i=1; i
            pre = max(pre + nums[i],nums[i]); 
            if(pre > result) result = pre;
        }
        return result;
    }
};

• 时间复杂度：O(n)
• 空间复杂度：O(1)

参考和推荐文章、视频

代码随想录 (programmercarl.com)https://programmercarl.com/0053.%E6%9C%80%E5%A4%A7%E5%AD%90%E5%BA%8F%E5%92%8C.html#%E6%80%9D%E8%B7%AF

代码随想录 (programmercarl.com)https://www.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#%E6%80%9D%E8%B7%AF

贪心算法的巧妙需要慢慢体会！LeetCode：53. 最大子序和_哔哩哔哩_bilibilihttps://www.bilibili.com/video/BV1aY4y1Z7ya/?spm_id_from=333.788&vd_source=a934d7fc6f47698a29dac90a922ba5a3

看起来复杂，其实是简单动态规划 | LeetCode：53.最大子序和_哔哩哔哩_bilibilihttps://www.bilibili.com/video/BV19V4y1F7b5/?spm_id_from=333.788&vd_source=a934d7fc6f47698a29dac90a922ba5a3

来自代码随想录的课堂截图：