leetCode 53.最大子数组和 动态规划 + 优化空间复杂度

关于此题我的往期文章：

leetCode 53.最大子数和 图解 + 贪心算法/动态规划+优化_呵呵哒(￣▽￣)"的博客-CSDN博客https://heheda.blog.csdn.net/article/details/13349726853. 最大子数组和 - 力扣（LeetCode）

>>思路和分析

子数组：其实就是连续的子序列

• 思考：求这个数组的最大子序和是多少？什么是最大子序和？

其实指的就是它的子数组的最大和，子数组其实就是连续的子序列。也就是在数组里边，找到一个连续的子序列，它的和一定是所有的连续子序列里边最大的，最后把这个和输出来。

>>动规五部曲

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

• dp[i]：包括下标i（以nums[i]为结尾）的最大连续子序列的和 为 dp[i]

2.确定递推公式

重要关键词：“延续”和 “不延续”

• 情况① “延续” 着前面的子序列，继续前面的子序列的和我继续累加着，
  • 即dp[i] = dp[i-1] + nums[i];
• 情况② “不延续” 着前面的子序列，前面的子序列的和我不要了，从我这里从头开始计算，
  • dp[i] = nums[i];

故dp[i]只有两个方向可以推出来

• dp[i-1] + nums[i]，即:nums[i]加入当前连续子序列和
• nums[i]，即：从头开始计算当前连续子序列和

一共就这两种情况，取它们的最大值，所以dp[i] = max(dp[i-1]+nums[i],nums[i]);

3.dp数组初始化

从递推公式可知，dp[i] 依赖于 dp[i-1] 的状态，dp[0]是递推公式的基础

• dp[0] = nums[0]
• 非0下标的值初始化成什么都可以，因为都会被覆盖掉

因此可统一初始化dp数组为0,dp[0]单独赋值，即

• vectordp(nums.size(),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[0] = nums[0];
        int result = dp[0];// 注意点！
        for(int i=1;isize();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;
        vector<int>dp(2,0);
        dp[0] = nums[0];
        int result = dp[0];// 注意点！
        for(int i=1;isize();i++) {
            dp[i % 2] = max(dp[(i-1) % 2]+nums[i],nums[i]);// 状态转移公式
            if(dp[i % 2] > result) result = dp[i % 2];// result 保存dp[i]的最大值
        }
        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%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/BV19V4y1F7b5/?spm_id_from=333.788&vd_source=a934d7fc6f47698a29dac90a922ba5a3推荐我的往期文章：leetCode 53.最大子数和 图解 + 贪心算法/动态规划+优化_呵呵哒(￣▽￣)"的博客-CSDN博客https://heheda.blog.csdn.net/article/details/133497268