LeetCode 一题多解 | 53. 最大子数组和:五种解法完全手册

    作者:nettee
公众号:面向大象编程

一、原题描述

LeetCode 53. Maximum Subarray 最大子序和

LeetCode 一题多解 | 53. 最大子数组和:五种解法完全手册

二、全部解法

本文将介绍「最大子数组和」问题的以下五种解法:

LeetCode 一题多解 | 53. 最大子数组和:五种解法完全手册

其中,动态规划和贪心法其实是殊途同归,得到的是同样一份代码。分治法虽然时间复杂度不占优,却是最考验解题思路的一种方法。

本文对不同的解法都进行了时间复杂度的分析。关于时间复杂度的分析技巧可以参考文章:时间复杂度分析快速入门:题型分类法

1. 暴力法:时间

暴力法是最容易想到的解法。我们可以直接根据题意,穷举各种可能的「子数组和」。

public int maxSubArray(int[] nums) {
    int n = nums.length;
    int res = Integer.MIN_VALUE;
    // 穷举各种可能的子数组 nums[i..j]
    for (int i = 0; i < n; i++) {
        for (int j = i; j < n; j++) {
            // 计算子数组 nums[i..j] 的和
            int sum = 0;
            for (int k = i; k <= j; k++) {
                sum += nums[k];                    
            }
            res = Math.max(res, sum);
        }
    }
    return res;
}

这个算法使用了三重循环,其中两层循环用于穷举所有可能的子数组,一层循环用于计算某个子数组的和。因此,算法的时间复杂度是 。

2. 暴力法的改进:时间

暴力法中使用的三重循环让时间复杂度变得非常大。我们可以通过一点简单的改进就能去掉一重循环,减少时间复杂度。

在上面的代码中,我们在第一层循环确定一个变量 i,然后在第二层循环依次计算 nums[i..i]nums[i..i+1] 一直到 nums[i..n-1] 的和。我们可以直接在一个 sum 变量上依次累加,而不需要使用第三层循环进行累加。

修改后的代码如下:

public int maxSubArray(int[] nums) {
    int n = nums.length;
    int res = Integer.MIN_VALUE;
    for (int i = 0; i < n; i++) {
        int sum = 0;
        for (int j = i; j < n; j++) {
            sum += nums[j];
            res = Math.max(res, sum);
        }
    }
    return res;
}

这个算法只用了两重循环。我们在暴力法基础上进行简单的改进,就使得时间复杂度从 减少到了 。

3. 分治法:时间

分治法不是这道题时间复杂度最优的解法,但可能是这道题最有挑战性的解法。分治法的算法设计、时间复杂度分析都并不容易。这个解法建议详细阅读,赶时间的同学可以先跳到下一个解法。

既然是分治法,我们首先要考虑的就是如何「分」。要计算数组 nums 的最大子数组和,我们从数组中间将数组一分为二,则子数组可能位于:

  • 左半部分数组
  • 右半部分数组
  • 中间(穿过中间线)
LeetCode 一题多解 | 53. 最大子数组和:五种解法完全手册
将数组一分为二后,子数组可能位于的三个位置

其中,位于左半部分数组和位于右半部分数组的子数组,可以通过递归调用继续求解,这便是分治法的「治」。

对于穿过中间线的子数组,我们可以分别计算「中间线左侧的最大子数组和」以及「中间线右侧的最大子数组和」,把它们相加就得到「穿过中间线的最大子数组和」。

LeetCode 一题多解 | 53. 最大子数组和:五种解法完全手册
穿过中间线的子数组分左右两半计算

将以上思路写成代码,我们可以得到以下的题解代码:

public int maxSubArray(int[] nums) {
    return maxSubArray(nums, 0, nums.length - 1);
}

// 计算 nums[lo..hi] 的最大子数组和
// lo 表示 low,hi 表示 high
private int maxSubArray(int[] nums, int lo, int hi) {
    if (hi < lo) {
        return Integer.MIN_VALUE;
    } else if (hi == lo) {
        return nums[lo];
    }
    
    int mid = lo + (hi - lo) / 2;
    // 计算左半部分数组的最大子数组和
    int max_left = maxSubArray(nums, lo, mid);
    // 计算右半部分数组的最大子数组和
    int max_right = maxSubArray(nums, mid+1, hi);
    // 计算穿过中间线的子数组的最大和
    int max_mid = maxMidSubArray(nums, lo, mid, hi);
    return Math.max(max_left, Math.max(max_mid, max_right));
}

private int maxMidSubArray(int[] nums, int lo, int mid, int hi) {
    // 计算中间线左侧(且紧挨着中间线)的最大子数组和
    int max_mid_left = 0;
    if (mid >= lo) {
        max_mid_left = nums[mid];
        int sum = 0;
        for (int i = mid; i >= lo; i--) {
            sum += nums[i];
            max_mid_left = Math.max(max_mid_left, sum);
        }
    }
    
    // 计算中间线右侧(且紧挨着中间线)的最大子数组和
    int max_mid_right = 0;
    if (mid + 1 <= hi) {
        max_mid_right = nums[mid+1];
        int sum = 0;
        for (int i = mid + 1; i <= hi; i++) {
            sum += nums[i];
            max_mid_right = Math.max(max_mid_right, sum);
        }
    }
    
    return max_mid_left + max_mid_right;
}

分治法的代码是写出来了,那么怎么证明这个算法的时间复杂度就是 呢?

其实,我们可以把这个算法跟经典的「归并排序」做个对照,两者是非常相似的:

  • 在「分」的过程,都是将数组平均分成了两半;
  • 在「治」的过程,都是对数组的左右两半做递归调用;
  • 都需要做一个额外的操作,这个算法中是计算穿过中间线的最大子数组,归并排序中是将左右两侧排好序的数组进行 merge,额外操作的时间复杂度都是 。

既然这个算法在各方面都可以和归并排序对应上,那么这个算法的时间复杂度一定也和归并排序一样,是 。

4. 动态规划:时间

动态规划的基本思路

这道题的动态规划解法在文章「子数组类问题的动态规划技巧」中讲解过。本文重新梳理了之前的讲解,还会讨论空间优化的方法。

我们还是使用动态规划的「解题四步骤」求解(关于四步骤的基础讲解,可以参考这篇文章):

  • 定义子问题
  • 写出子问题的递推关系
  • 确定 DP 数组的计算顺序
  • 空间优化

由于这道题计算的是「最大子数组和」,我们使用一个「子数组」类题目的常见技巧,在定义子问题的时候加上位于数组尾部的限制条件。

我们定义子问题 表示「nums[0..k) 中,以最后一个元素结尾的最大子数组和」,那么原问题可以表示为 。

LeetCode 一题多解 | 53. 最大子数组和:五种解法完全手册
动态规划的子问题

在子问题中限制结果位于数组尾部,是为了将当前的最优结果跟后面新加入的元素能够拼接起来,如下图所示:

LeetCode 一题多解 | 53. 最大子数组和:五种解法完全手册
子问题中限制结果位于数组尾部的原因

接着,我们写出子问题的递推关系:

这个递推公式的含义是,计算 nums[0..k) 的最大子数组和时,要么是把新元素 nums[k-1] 加入前一个子问题的结果(即 的含义),要么是只使用元素 nums[k-1],选择其中结果较大的一个方案。

这个递推公式可以化简为:

可以看到,子问题的依赖关系非常简单,在计算 DP 数组时,从左到右计算即可。这样我们可以写出如下的题解代码:

public int maxSubArray(int[] nums) {
    // 子问题:
    // f(k) = nums[0..k) 中以 nums[k-1] 结尾的最大子数组和
    // 原问题 = max{ f(k) }, 0 <= k <= N

    // f(0) = 0
    // f(k) = max{ f(k-1), 0 } + nums[k-1]

    int N = nums.length;
    int[] dp = new int[N+1];
    dp[0] = 0;

    int res = Integer.MIN_VALUE;
    for (int k = 1; k <= N; k++) {
        dp[k] = Math.max(dp[k-1], 0) + nums[k-1];
        res = Math.max(res, dp[k]);
    }
    return res;
}

时间复杂度 ,空间复杂度 。

动态规划的空间优化

上面的动态规划代码已经非常高效了。不过经过一些空间优化手段,可以让代码更加简洁,也可以让空间复杂度降低到 。

首先,由于每个子问题只需要通过上一个子问题计算出来,我们不需要保存整个一维 DP 数组,用单个变量保存即可:

public int maxSubArray(int[] nums) {
    int dp = 0;
    int res = Integer.MIN_VALUE;
    for (int k = 1; k <= nums.length; k++) {
        dp = Math.max(dp, 0) + nums[k-1];
        res = Math.max(res, dp);
    }
    return res;
}

其中的 for 循环还可以做下标优化,变成 for-each 循环:

public int maxSubArray(int[] nums) {
    int dp = 0;
    int res = Integer.MIN_VALUE;
    for (int n : nums) {
        dp = Math.max(dp, 0) + n;
        res = Math.max(res, dp);
    }
    return res;
}

这样,我们就得到了时间复杂度 、空间复杂度 的动态规划解法。

5. 贪心法:时间

使用贪心法可以写出这道题最简洁、最高效的代码:

public int maxSubArray(int[] nums) {
    int sum = 0// 计算当前的部分子数组和
    int res = Integer.MIN_VALUE;
    for (int n : nums) {
        // 如果部分和小于零,直接舍弃,从零开始重新累加
        if (sum < 0) {
            sum = 0;
        }
        sum += n; // 加上当前元素
        res = Math.max(res, sum);
    }
    return res;
}

这段贪心法代码的时间复杂度是 ,空间复杂度是 。

不过,贪心法的一大劣势是很难证明其正确性。例如,上面的代码中只做了一重循环,并没有遍历所有可能的子数组,为什么最终找到的一定是最大子数组和?如果凭空思考的话,确实很难证明这段代码的正确性。

因此,在面试中我们尽量不要写贪心法的代码,代码是容易写了,但是要说明代码正确可不容易。

不过对于这道题,我们可以将贪心法和动态规划解法联系起来,从而理解贪心法的代码究竟做了什么。

实际上,仔细观察上面的动态规划代码和贪心法代码,我们可以发现,动态规划代码做一点等价变换,再改个变量名,就得到了贪心法的代码!

也就是说,贪心法实际上是从另一个角度描述了空间优化后的动态规划解法

贪心法代码中的 sum 变量可以理解为动态规划的当前子问题,即「以当前元素结尾的最大子数组和」。而动态规划子问题的递推关系为:

当前子问题如果小于 0,在计算 的时候直接会被 取代掉,不会对结果有任何影响。这就是为什么贪心法代码中,当 sum < 0 的时候,会直接舍弃,从 0 重新开始累加的原因。

在很多题目中,贪心法都是动态规划的特例。用贪心法能解决的问题一般也可以用动态规划求解。后面我们还会遇到这样的题目。

总结

如果在面试中遇到了这个问题,我们应该回答哪些解法呢?我的建议是:先回答暴力法的改进版,再回答动态规划解法。

  • 一般来说,面试官期望你给出的解法是动态规划解法。那么动态规划解法是必须要掌握的,而且最好对空间优化方法非常熟练。

  • 而回答暴力解法,是为了给面试官展示解决算法题的基本思路:先给出一个暴力解法,保证题目做出来,确定时间复杂度的上限,再想办法优化题目。

关于其他的解法,要注意几点:

  • 如果你一上来就很快写出了动态规划解法,也许你思路很快,但面试官会怀疑你是不是背题了,反而对你有一些不好的印象。

  • 如果你直接写出了贪心法,面试官会让你证明解法的正确性。但是这道题的贪心正确性证明有些难度,不太容易说得清楚。因此,最好不要在面试的时候使用贪心法。

  • 至于分治法的解法,一般情况下面试中不会涉及。不过如果面试官考察得非常全面,会让你尝试用分治法进行求解。这时候如果你能够顺利写出分治法的代码,会是一个很大的加分项。

其实,掌握一道题的多种解法,可以在面试中做到游刃有余,选择最合适的解法进行回答。后面我还会更新一些 LeetCode 经典题目的一题多解讲解,敬请期待。

原创不易,欢迎分享、点赞和「在看」 ⇩

原文始发于微信公众号(面向大象编程):LeetCode 一题多解 | 53. 最大子数组和:五种解法完全手册

本文由 程序员小吴 创作,采用 CC BY 3.0 CN协议 进行许可。 可自由转载、引用,但需署名作者且注明文章出处。如转载至微信公众号,请在先添加作者公众号二维码。
五分钟学算法 » LeetCode 一题多解 | 53. 最大子数组和:五种解法完全手册

我还会在以下平台发布内容

GitHub 哔哩哔哩