写在前面
在 LeetCode 上有一道"备受争议"的题目。
该题长期作为 拼多多题库中的打榜题 ：
据同学们反映，该题还是 清华大学 和 南京大学 考研专业课中的算法题。
其中南京大学的出题人，还真贴心地针对不同解法，划分不同分值：
细翻评论区。
不仅是拼多多，该题还在诸如 神州信息 和 滴滴出行 这样的互联网大厂笔试中出现过：
但，这都不是这道题"备受争议"的原因。
这道题最魔幻的地方是：常见解法可做到 O(n) 时间，O(1) 空间，而进阶做法最快也只能做到 O(n) 时间，O(logn) 空间。
称作"反向进阶"也不为过。
接下来，我将从常规解法的两种理解入手，逐步进阶到考研/笔面中分值更高的进阶做法，帮助大家在这题上做到尽善尽美。
毕竟在一道算法题上做到极致，比背一段大家都会"八股文"，在笔面中更显价值。
题目描述
平台：LeetCode
题号：LCR 161 或 53
给你一个整数数组 nums，请你找出一个具有最大和的连续子数组（子数组最少包含一个元素），返回其最大和。
子数组是数组中的一个连续部分。
示例 1：
输入：nums = [-2,1,-3,4,-1,2,1,-5,4]
输出：6
解释：连续子数组 [4,-1,2,1] 的和最大，为 6 。
示例 2：
输入：nums = [1]
输出：1
示例 3：
输入：nums = [5,4,-1,7,8]
输出：23
提示：
- 1<=nums.length<=105
- −104<=nums[i]<=104
进阶：如果你已经实现复杂度为 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]=max(f[i−1]+nums[i],nums[i])
由于 f[i] 仅依赖于 f[i−1] 进行转移，可使用有限变量进行优化，因此写出来的代码也是和上述前缀和角度分析的类似。
Java 代码：
class 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++ 代码：
class 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 代码：
class 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 代码：
function 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=⌊2l+r⌋
随后考虑如何用“子问题”的解合并成“原问题”的解：
- 合并区间和 (
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 代码：
class Solution {
int[] dfs(int[] nums, int l, int r) {
if (l == r) {
int t = Math.max(nums[l], 0);
return new int[]{nums[l], t, t, t};
}
int mid = l + r >> 1;
int[] left = dfs(nums, l, mid), right = dfs(nums, mid + 1, r);
int[] ans = new int[4];
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(Math.max(left[3], right[3]), left[2] + right[1]);
return ans;
}
public int maxSubArray(int[] nums) {
int m = nums[0];
for (int x : nums) m = Math.max(m, x);
if (m <= 0) return m;
return dfs(nums, 0, nums.length - 1)[3];
}
}
C++ 代码：
class Solution {
public:
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 代码：
class 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 代码：
function 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)
- 空间复杂度：递归需要函数栈空间，算法每次将当前数组一分为二，进行递归处理，递归层数为 logn，即函数栈最多有 logn 个函数栈帧，复杂度为 O(logn)
总结
虽然，这道题的进阶做法相比常规做法，在时空复杂度上没有优势。
但进阶做法的分治法更具有 进一步拓展 的价值，容易展开为支持「区间修改，区间查询」的高级数据结构 - 线段树。
实际上，上述的进阶「分治法」就是线段树的"建树"过程。
这也是为什么「分治法」在名校考研课中分值更大，在大厂笔面中属于必选解法的原因，希望大家重点掌握。
作者：宫水三叶的刷题日记
来源：juejin.cn/post/7310104657211293723
