标签搜索

目 录CONTENT

文章目录

动态规划套路:最大子数组和.md

小小城
2021-08-22 / 0 评论 / 0 点赞 / 4 阅读 / 1,837 字 / 正在检测是否收录...
温馨提示:
本文最后更新于 2022-05-02,若内容或图片失效,请留言反馈。部分素材来自网络,若不小心影响到您的利益,请联系我们删除。

动态规划套路:最大子数组和

@[toc]

一、题目描述

这次看一个简答的题:
在这里插入图片描述

二、分析

这道题比较简单,主要是回顾动态 规划的解法!

  •  其实第一次看到这道题,我首先想到的是滑动窗口算法,因为我们说过,滑动窗口算法就是专门处理子串/子数组问题的,这里不就是子数组问题么?
  •  但是,稍加分析就发现,这道题还不能用滑动窗口算法,因为数组中的数字可以是负数
  •  滑动窗口算法无非就是双指针形成的窗口扫描整个数组/子串,但关键是,你得清楚地知道什么时候应该移动右侧指针来扩大窗口,什么时候移动左侧指针来减小窗口。
  •  而对于这道题目,你想想,当窗口扩大的时候可能遇到负数,窗口中的值也就可能增加也可能减少,这种情况下不知道什么时机去收缩左侧窗口,也就无法求出「最大子数组和」。
  •  解决这个问题需要动态规划技巧,但是dp数组的定义比较特殊。按照我们常规的动态规划思路,一般是这样定义dp数组:

nums[0..i]中的「最大的子数组和」为dp[i]

  •  如果这样定义的话,整个nums数组的「最大子数组和」就是dp[n-1]。如何找状态转移方程呢?按照数学归纳法,假设我们知道了dp[i-1],如何推导出dp[i]呢?
  •  如下图,按照我们刚才对dp数组的定义,dp[i] = 5,也就是等于nums[0..i]中的最大子数组和:
    在这里插入图片描述
  •  那么在上图这种情况中,利用数学归纳法,你能用dp[i]推出dp[i+1]吗?
  •  实际上是不行的,因为子数组一定是连续的,按照我们当前dp数组定义,并不能保证nums[0..i]中的最大子数组与nums[i+1]是相邻的,也就没办法从dp[i]推导出dp[i+1]。
  •  所以说我们这样定义dp数组是不正确的,无法得到合适的状态转移方程。对于这类子数组问题,我们就要重新定义dp数组的含义:

以nums[i]为结尾的「最大子数组和」为dp[i]。

  •  这种定义之下,想得到整个nums数组的「最大子数组和」,不能直接返回dp[n-1],而需要遍历整个dp数组
int res = Integer.MIN_VALUE;
for (int i = 0; i < n; i++) {
    res = Math.max(res, dp[i]);
}
return res;
  •  依然使用数学归纳法来找状态转移关系:假设我们已经算出了dp[i-1],如何推导出dp[i]呢?
  •  可以做到,dp[i]有两种「选择」,要么与前面的相邻子数组连接,形成一个和更大的子数组;要么不与前面的子数组连接,自成一派,自己作为一个子数组。
  •  如何选择?既然要求「最大子数组和」,当然选择结果更大的那个啦:
// 要么自成一派,要么和前面的子数组合并
dp[i] = Math.max(nums[i], nums[i] + dp[i - 1]);

综上,我们已经写出了状态转移方程,就可以直接写出解法了:

int maxSubArray(int[] nums) {
    int n = nums.length;
    if (n == 0) return 0;
    int[] dp = new int[n];
    // base case
    // 第一个元素前面没有子数组
    dp[0] = nums[0];
    // 状态转移方程
    for (int i = 1; i < n; i++) {
        dp[i] = Math.max(nums[i], nums[i] + dp[i - 1]);
    }
    // 得到 nums 的最大子数组
    int res = Integer.MIN_VALUE;
    for (int i = 0; i < n; i++) {
        res = Math.max(res, dp[i]);
    }
    return res;
}

以上解法时间复杂度是 O(N),空间复杂度也是 O(N),较暴力解法已经很优秀了,不过注意到dp[i]仅仅和dp[i-1]的状态有关,那么我们可以进行「状态压缩」,将空间复杂度降低

int maxSubArray(int[] nums) {
    int n = nums.length;
    if (n == 0) return 0;
    // base case
    int dp_0 = nums[0];
    int dp_1 = 0, res = dp_0;

    for (int i = 1; i < n; i++) {
        // dp[i] = max(nums[i], nums[i] + dp[i-1])
        dp_1 = Math.max(nums[i], nums[i] + dp_0);
        dp_0 = dp_1;
        // 顺便计算最大的结果
        res = Math.max(res, dp_1);
    }

    return res;
0

评论区