题目
给定一个整数数组
nums
,找到一个具有最大和的连续子数组(子数组最少包含一个元素),返回其最大和。示例:
1
2
3 输入: [-2,1,-3,4,-1,2,1,-5,4],
输出: 6
解释: 连续子数组 [4,-1,2,1] 的和最大,为 6。进阶:
如果你已经实现复杂度为 O(n) 的解法,尝试使用更为精妙的分治法求解。
思路
暴力法
遍历所有的连续子数组,时间复杂度$O(N^2)$。
动态规划
从第一个元素开始,记录以该元素为结尾的最大子序和,那么对于第$i$个元素,以它为结尾的最大子序和为$max(V_i,~dp[i-1]+V_i)$。
1 | class Solution { |
这种解法很容易得到时间复杂度$O(N)$。且由于只用到$dp[i]$和$dp[i-1]$,则可以用两个变量代替容器,空间复杂度优化为$O(1)$。
1 | class Solution { |
贪心算法
贪心算法的思路为不停将当前元素添加到子序中,更新最大值,若求和结果小于0,则重新开始计算子序和。
1 | class Solution { |
需要注意的点是
1 | ans = max(ans, curr); |
这两句的顺序,不能颠倒,因为在更新最大值之前清空当前子序和会导致错误。时间复杂度$O(N)$,空间复杂度$O(1)$。
分治算法
分治算法的思考
所谓分治算法,其实就是将一个数组一分为二,在两个数组中分别寻找拥有最大子序和的子序列。
使用到分治算法(Divide-Conquer)的经典算法有归并排序(Mergesort),其基本思想也是将一个需要排序的数组一分为二,对两个子数组进行分别排序。
以上两种问题要实现,都需要思考如何将两个子区间的结果进行正确的合并。比如归并排序中,我们需要思考:如何将左右两半已排序的数组合并成一个排序数组?答案是利用一个辅助数组和两个指针,分别指向两个已排序子数组的第一个元素,依次比较两个数组中的元素,将辅助数组中较小的元素插入主数组中较大元素的左侧(升序排序),然后辅助数组指针自加。
而在本问题中,我们要思考的则是如何根据两个子区间的最大子序和求出整个区间的最大子序和。很容易想到整个区间的最大子序和对应的连续子序列的位置有以下三种可能:
- 连续子序列在左子区间;
- 连续子序列在右子区间;
- 连续子序列横跨两个子区间。
接下来要思考的问题是:
我们需要哪些信息来合并子区间?
首先一定要知道子区间的最大子序和mSum
,因为我们至少需要比较两个子区间各自的最大子序和;其次为了将序列跨区间的情况考虑进去,我们表示以子区间的右边界为序列尾的最大子序和rsum
、以子区间左边界为序列首的最大子序和lsum
,以及整个子区间的区间和isum
(用于计算合并序列的lsum
与rsum
)。因此我们共需要序列的四个属性:- 区间[l, r]最大子序和
msum
- 区间[l, r]内以 l 为左端点的最大子序和
lsum
- 区间[l, r]内以 r 为右端点的最大子序和
rsum
- 区间[l, r]的区间和
isum
- 区间[l, r]最大子序和
我们如何根据这些信息进行合并?
这个问题其实也是如何根据两个子区间的信息计算合并区间的信息?- 对于
msum
整个区间的最大子序和,要么是左右子区间的msum
,要么是横跨两个区间的左区间的rsum
+右区间的lsum
; - 对于
lsum
要么是左子区间的lsum
,要么是左子区间的isum
+右子区间的lsum
; - 对于
rsum
要么是右子区间的rsum
,要么是右子区间的isum
+左子区间的rsum
; - 对于
isum
等于左、右子区间isum
之和。
其实到这里问题就已经得到了解决。接下来考虑的是如何实现。
- 对于
分治算法的实现
分治地对一个数组求最大子序和的步骤为:
- 将数组一分为二;
- 对左区间求最大子序和;
- 对右区间求最大子序和;
- 合并左右区间。
相应地,我们需要的API需要有以下功能:
- 求子区间最大子序和;
- 区间和并。
代码如下:
1 | class Solution { |
反思一下…lambda多余了,重新贴:
1 | class Solution { |
分治算法总结
- 时间复杂度:$O(N)$,因为还是相当于遍历了所有节点;
- 空间复杂度:$O(logN)$,因为递归深度为$logN$。
使用分治算法可以用于解决任意子区间的最大子序和问题,并且如果再牺牲一些空间复杂度来构建一棵线段树,可以实现$O(logN)$时间内的任意查询。分治算法的优势在大规模查询的情况下被体现出来;而以上的动态规划和贪心算法对于每一次查询都需要$O(n)$的时间复杂度,$n$为查询的子区间长度。