LC 53. 最大子数组和
题目描述
这是 LeetCode 上的 53. 最大子数组和 ,难度为 中等。
给你一个整数数组 nums
,请你找出一个具有最大和的连续子数组(子数组最少包含一个元素),返回其最大和。
子数组是数组中的一个连续部分。
示例 1:1
2
3
4
5输入:nums = [-2,1,-3,4,-1,2,1,-5,4]
输出:6
解释:连续子数组 [4,-1,2,1] 的和最大,为 6 。
示例 2:1
2
3输入:nums = [1]
输出:1
示例 3:1
2
3输入:nums = [5,4,-1,7,8]
输出:23
提示:
- $1 <= nums.length <= 10^5$
- $-10^4 <= nums[i] <= 10^4$
进阶:如果你已经实现复杂度为 $O(n)$ 的解法,尝试使用更为精妙的分治法求解。
前缀和 or 线性 DP
当要我们求「连续段」区域和的时候,要很自然的想到「前缀和」。
所谓前缀和,是指对原数组“累计和”的描述,通常是指一个与原数组等长的数组。
设前缀和数组为 sum
,sum
的每一位记录的是从「起始位置」到「当前位置」的元素和。例如 $sum[x]$ 是指原数组中“起始位置”到“位置 x
”这一连续段的元素和。
有了前缀和数组 sum
,当我们求连续段 $[i, j]$ 的区域和时,利用「容斥原理」,便可进行快速求解。
通用公式:ans = sum[j] - sum[i - 1]
。
由于涉及 -1
操作,为减少边界处理,我们可让前缀和数组下标从 $1$ 开始。在进行快速求和时,再根据原数组下标是否从 $1$ 开始,决定是否进行相应的下标偏移。
学习完一维前缀和后,回到本题。
先用 nums
预处理出前缀和数组 sum
,然后在遍历子数组右端点 j
的过程中,通过变量 m
动态记录已访问的左端点 i
的前缀和最小值。最终,在所有 sum[j] - m
的取值中选取最大值作为答案。
代码实现上,我们无需明确计算前缀和数组 sum
,而是使用变量 s
表示当前累计的前缀和(充当右端点),并利用变量 m
记录已访问的前缀和的最小值(充当左端点)即可。
本题除了将其看作为「前缀和裸题用有限变量进行空间优化」以外,还能以「线性 DP」角度进行理解。
定义 $f[i]$ 为考虑前 $i$ 个元素,且第 $nums[i]$ 必选的情况下,形成子数组的最大和。
不难发现,仅考虑前 $i$ 个元素,且 $nums[i]$ 必然参与的子数组中。要么是 $nums[i]$ 自己一个成为子数组,要么与前面的元素共同组成子数组。
因此,状态转移方程:
由于 $f[i]$ 仅依赖于 $f[i - 1]$ 进行转移,可使用有限变量进行优化,因此写出来的代码也是和上述前缀和角度分析的类似。
Java 代码:1
2
3
4
5
6
7
8
9
10
11class Solution {
public int maxSubArray(int[] nums) {
int s = 0, m = 0, ans = -10010;
for (int x : nums) {
s += x;
ans = Math.max(ans, s - m);
m = Math.min(m, s);
}
return ans;
}
}
C++ 代码:1
2
3
4
5
6
7
8
9
10
11
12class Solution {
public:
int maxSubArray(vector<int>& nums) {
int s = 0, m = 0, ans = -10010;
for (int x : nums) {
s += x;
ans = max(ans, s - m);
m = min(m, s);
}
return ans;
}
};
Python 代码:1
2
3
4
5
6
7
8class Solution:
def maxSubArray(self, nums: List[int]) -> int:
s, m, ans = 0, 0, -10010
for x in nums:
s += x
ans = max(ans, s - m)
m = min(m, s)
return ans
TypeScript 代码:1
2
3
4
5
6
7
8
9function maxSubArray(nums: number[]): number {
let s = 0, m = 0, ans = -10010;
for (let x of nums) {
s += x;
ans = Math.max(ans, s - m);
m = Math.min(m, s);
}
return ans;
};
- 时间复杂度:$O(n)$
- 空间复杂度:$O(1)$
分治
“分治法”的核心思路是将大问题拆分成更小且相似的子问题,通过递归解决这些子问题,最终合并子问题的解来得到原问题的解。
实现分治,关键在于对“递归函数”的设计(入参 & 返回值)。
在涉及数组的分治题中,左右下标 l
和 r
必然会作为函数入参,因为它能用于表示当前所处理的区间,即小问题的范围。
对于本题,仅将最大子数组和(答案)作为返回值并不足够,因为单纯从小区间的解无法直接推导出大区间的解,我们需要一些额外信息来辅助求解。
具体的,我们可以将返回值设计成四元组,分别代表 区间和
,前缀最大值
,后缀最大值
和 最大子数组和
,用 [sum, lm, rm, max]
表示。
有了完整的函数签名 int[] dfs(int[] nums, int l, int r)
,考虑如何实现分治:
- 根据当前区间 $[l, r]$ 的长度进行分情况讨论:
- 若 $l = r$,只有一个元素,区间和为 $nums[l]$,而 最大子数组和、前缀最大值 和 后缀最大值 由于允许“空数组”,因此均为 $\max(nums[l], 0)$
- 否则,将当前问题划分为两个子问题,通常会划分为两个相同大小的子问题,划分为 $[l, mid]$ 和 $[mid + 1, r]$ 两份,递归求解,其中 $mid = \left \lfloor \frac{l + r}2{} \right \rfloor$
随后考虑如何用“子问题”的解合并成“原问题”的解:
- 合并区间和 (
sum
): 当前问题的区间和等于左右两个子问题的区间和之和,即sum = left[0] + right[0]
。 - 合并前缀最大值 (
lm
): 当前问题的前缀最大值可以是左子问题的前缀最大值,或者左子问题的区间和加上右子问题的前缀最大值。即lm = max(left[1], left[0] + right[1])
。 - 合并后缀最大值 (
rm
): 当前问题的后缀最大值可以是右子问题的后缀最大值,或者右子问题的区间和加上左子问题的后缀最大值。即rm = max(right[2], right[0] + left[2])
。 - 合并最大子数组和 (
max
): 当前问题的最大子数组和可能出现在左子问题、右子问题,或者跨越左右两个子问题的边界。因此,max
可以通过max(left[3], right[3], left[2] + right[1])
来得到。
一些细节:由于我们在计算 lm
、rm
和 max
的时候允许数组为空,而答案对子数组的要求是至少包含一个元素。因此对于 nums
全为负数的情况,我们会错误得出最大子数组和为 0
的答案。针对该情况,需特殊处理,遍历一遍 nums
,若最大值为负数,直接返回最大值。
Java 代码:
1 |
|
C++ 代码:1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26class Solution {
public:
// 返回值: [sum, lm, rm, max] = [区间和, 前缀最大值, 后缀最大值, 最大子数组和]
vector<int> dfs(vector<int>& nums, int l, int r) {
if (l == r) {
int t = max(nums[l], 0);
return {nums[l], t, t, t};
}
// 划分成两个子区间,分别求解
int mid = l + r >> 1;
auto left = dfs(nums, l, mid), right = dfs(nums, mid + 1, r);
// 组合左右子区间的信息,得到当前区间的信息
vector<int> ans(4);
ans[0] = left[0] + right[0]; // 当前区间和
ans[1] = max(left[1], left[0] + right[1]); // 当前区间前缀最大值
ans[2] = max(right[2], right[0] + left[2]); // 当前区间后缀最大值
ans[3] = max({left[3], right[3], left[2] + right[1]}); // 最大子数组和
return ans;
}
int maxSubArray(vector<int>& nums) {
int m = nums[0];
for (int x : nums) m = max(m, x);
if (m <= 0) return m;
return dfs(nums, 0, nums.size() - 1)[3];
}
};
Python 代码:1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21class Solution:
def maxSubArray(self, nums: List[int]) -> int:
def dfs(l, r):
if l == r:
t = max(nums[l], 0)
return [nums[l], t, t, t]
# 划分成两个子区间,分别求解
mid = (l + r) // 2
left, right = dfs(l, mid), dfs(mid + 1, r)
# 组合左右子区间的信息,得到当前区间的信息
ans = [0] * 4
ans[0] = left[0] + right[0] # 当前区间和
ans[1] = max(left[1], left[0] + right[1]) # 当前区间前缀最大值
ans[2] = max(right[2], right[0] + left[2]) # 当前区间后缀最大值
ans[3] = max(left[3], right[3], left[2] + right[1]) # 最大子数组和
return ans
m = max(nums)
if m <= 0:
return m
return dfs(0, len(nums) - 1)[3]
TypeScript 代码:1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22function maxSubArray(nums: number[]): number {
const dfs = function (l: number, r: number): number[] {
if (l == r) {
const t = Math.max(nums[l], 0);
return [nums[l], t, t, t];
}
// 划分成两个子区间,分别求解
const mid = (l + r) >> 1;
const left = dfs(l, mid), right = dfs(mid + 1, r);
// 组合左右子区间的信息,得到当前区间的信息
const ans = Array(4).fill(0);
ans[0] = left[0] + right[0]; // 当前区间和
ans[1] = Math.max(left[1], left[0] + right[1]); // 当前区间前缀最大值
ans[2] = Math.max(right[2], right[0] + left[2]); // 当前区间后缀最大值
ans[3] = Math.max(left[3], right[3], left[2] + right[1]); // 最大子数组和
return ans;
}
const m = Math.max(...nums);
if (m <= 0) return m;
return dfs(0, nums.length - 1)[3];
};
- 时间复杂度:$O(n)$
- 空间复杂度:$O(\log{n})$
最后
这是我们「刷穿 LeetCode」系列文章的第 No.53
篇,系列开始于 2021/01/01,截止于起始日 LeetCode 上共有 1916 道题目,部分是有锁题,我们将先把所有不带锁的题目刷完。
在这个系列文章里面,除了讲解解题思路以外,还会尽可能给出最为简洁的代码。如果涉及通解还会相应的代码模板。
为了方便各位同学能够电脑上进行调试和提交代码,我建立了相关的仓库:https://github.com/SharingSource/LogicStack-LeetCode 。
在仓库地址里,你可以看到系列文章的题解链接、系列文章的相应代码、LeetCode 原题链接和其他优选题解。
本博客所有文章除特别声明外,均采用 CC BY-SA 4.0 协议 ,转载请注明出处!