美文网首页面试精选
动态规划设计:最大子数组

动态规划设计:最大子数组

作者: labuladong | 来源:发表于2020-11-13 23:57 被阅读0次

    读完本文,你可以去力扣拿下如下题目:

    53.最大子序和

    -----------

    最大子数组问题和前文讲过的 经典动态规划:最长递增子序列 的套路非常相似,代表着一类比较特殊的动态规划问题的思路:

    title

    思路分析

    其实第一次看到这道题,我首先想到的是滑动窗口算法,因为我们前文说过嘛,滑动窗口算法就是专门处理子串/子数组问题的,这里不就是子数组问题么?

    但是,稍加分析就发现,这道题还不能用滑动窗口算法,因为数组中的数字可以是负数

    滑动窗口算法无非就是双指针形成的窗口扫描整个数组/子串,但关键是,你得清楚地知道什么时候应该移动右侧指针来扩大窗口,什么时候移动左侧指针来减小窗口。

    而对于这道题目,你想想,当窗口扩大的时候可能遇到负数,窗口中的值也就可能增加也可能减少,这种情况下不知道什么时机去收缩左侧窗口,也就无法求出「最大子数组和」。

    解决这个问题需要动态规划技巧,但是 dp 数组的定义比较特殊。按照我们常规的动态规划思路,一般是这样定义 dp 数组:

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

    如果这样定义的话,整个 nums 数组的「最大子数组和」就是 dp[n-1]。如何找状态转移方程呢?按照数学归纳法,假设我们知道了 dp[i-1],如何推导出 dp[i] 呢?

    如下图,按照我们刚才对 dp 数组的定义,dp[i] = 5 ,也就是等于 nums[0..i] 中的最大子数组和:

    image

    那么在上图这种情况中,利用数学归纳法,你能用 dp[i] 推出 dp[i+1] 吗?

    实际上是不行的,因为子数组一定是连续的,按照我们当前 dp 数组定义,并不能保证 nums[0..i] 中的最大子数组与 nums[i+1] 是相邻的,也就没办法从 dp[i] 推导出 dp[i+1]

    所以说我们这样定义 dp 数组是不正确的,无法得到合适的状态转移方程。对于这类子数组问题,我们就要重新定义 dp 数组的含义:

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

    PS:我认真写了 100 多篇原创,手把手刷 200 道力扣题目,全部发布在 labuladong的算法小抄,持续更新。建议收藏,按照我的文章顺序刷题,掌握各种算法套路后投再入题海就如鱼得水了。

    这种定义之下,想得到整个 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;
    }
    

    最后总结

    虽然说动态规划推状态转移方程确实比较玄学,但大部分还是有些规律可循的。

    今天这道「最大子数组和」就和「最长递增子序列」非常类似,dp 数组的定义是「以 nums[i] 为结尾的最大子数组和/最长递增子序列为 dp[i]」。因为只有这样定义才能将 dp[i+1]dp[i] 建立起联系,利用数学归纳法写出状态转移方程。

    _____________

    我的 在线电子书 有 100 篇原创文章,手把手带刷 200 道力扣题目,建议收藏!对应的 GitHub 算法仓库 已经获得了 70k star,欢迎标星!

    相关文章

      网友评论

        本文标题:动态规划设计:最大子数组

        本文链接:https://www.haomeiwen.com/subject/bjopbktx.html