作者：nettee
公众号：面向大象编程
一、原题描述
LeetCode 53. Maximum Subarray 最大子序和
二、全部解法
本文将介绍「最大子数组和」问题的以下五种解法：
其中，动态规划和贪心法其实是殊途同归，得到的是同样一份代码。分治法虽然时间复杂度不占优，却是最考验解题思路的一种方法。
本文对不同的解法都进行了时间复杂度的分析。关于时间复杂度的分析技巧可以参考文章：时间复杂度分析快速入门：题型分类法。
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 的最大子数组和，我们从数组中间将数组一分为二，则子数组可能位于：
-
左半部分数组 -
右半部分数组 -
中间（穿过中间线）
其中，位于左半部分数组和位于右半部分数组的子数组，可以通过递归调用继续求解，这便是分治法的「治」。
对于穿过中间线的子数组，我们可以分别计算「中间线左侧的最大子数组和」以及「中间线右侧的最大子数组和」，把它们相加就得到「穿过中间线的最大子数组和」。
将以上思路写成代码，我们可以得到以下的题解代码：
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) 中，以最后一个元素结尾的最大子数组和」，那么原问题可以表示为 。
在子问题中限制结果位于数组尾部，是为了将当前的最优结果跟后面新加入的元素能够拼接起来，如下图所示：
接着，我们写出子问题的递推关系：
这个递推公式的含义是，计算 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. 最大子数组和：五种解法完全手册
