LeetCode 一题多解 | 53. 最大子数组和:五种解法完全手册
点击上方“五分钟学算法”,选择“星标”公众号重磅干货,第一时间送达作者:nettee 公众号:面向大象编程一、原题描述 LeetCode 53. Maximum S...
点击上方“五分钟学算法”,选择“星标”公众号
重磅干货,第一时间送达
作者:nettee
公众号:面向大象编程
一、原题描述
LeetCode 53. Maximum Subarray 最大子序和
![](https://i-blog.csdnimg.cn/blog_migrate/2a963f9ef04e6cde6f66c3707c68e0ce.png)
二、全部解法
本文将介绍「最大子数组和」问题的以下五种解法:
其中,动态规划和贪心法其实是殊途同归,得到的是同样一份代码。分治法虽然时间复杂度不占优,却是最考验解题思路的一种方法。
本文对不同的解法都进行了时间复杂度的分析。关于时间复杂度的分析技巧可以参考文章:时间复杂度分析快速入门:题型分类法。
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
的最大子数组和,我们从数组中间将数组一分为二,则子数组可能位于:
左半部分数组
右半部分数组
中间(穿过中间线)
![](https://i-blog.csdnimg.cn/blog_migrate/74c1a7d4ff4207ac475439c11ede8454.png)
其中,位于左半部分数组和位于右半部分数组的子数组,可以通过递归调用继续求解,这便是分治法的「治」。
对于穿过中间线的子数组,我们可以分别计算「中间线左侧的最大子数组和」以及「中间线右侧的最大子数组和」,把它们相加就得到「穿过中间线的最大子数组和」。
![](https://i-blog.csdnimg.cn/blog_migrate/be0c9c3f9b25e4f0086979b1c2441b1f.png)
将以上思路写成代码,我们可以得到以下的题解代码:
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)
中,以最后一个元素结尾的最大子数组和」,那么原问题可以表示为
。
![](https://i-blog.csdnimg.cn/blog_migrate/7fbe6d0c30331ce427be44fa07e785ca.png)
在子问题中限制结果位于数组尾部,是为了将当前的最优结果跟后面新加入的元素能够拼接起来,如下图所示:
![](https://i-blog.csdnimg.cn/blog_migrate/f1bdb256d47e15f167a85c654db10a8a.png)
接着,我们写出子问题的递推关系:
这个递推公式的含义是,计算 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 经典题目的一题多解讲解,敬请期待。
---
由 五分钟学算法 原班人马打造的公众号:图解面试算法,现已正式上线!
接下来我们将会在该公众号上,为大家分享优质的算法解题思路,坚持每天一篇原创文章的输出,视频动画制作不易,感兴趣的小伙伴可以关注点赞一下哈!
![Logo](https://devpress.csdnimg.cn/79de2bf0b7994defa4242ef90d5513fa.jpg)
开放原子开发者工作坊旨在鼓励更多人参与开源活动,与志同道合的开发者们相互交流开发经验、分享开发心得、获取前沿技术趋势。工作坊有多种形式的开发者活动,如meetup、训练营等,主打技术交流,干货满满,真诚地邀请各位开发者共同参与!
更多推荐
所有评论(0)