做算法题这些年我见过最多的一道题不是红黑树也不是什么冷门数据结构而是这个给定一个整数数组找出一个具有最大和的连续子数组返回这个最大和。这就是最大连续子序列和算法很多人也叫它最大子段和问题。我第一次接触它是在某平台刷题时卡了很久明明暴力解能跑却总觉得“应该还有更快的方法”。后来把它从暴力到分治再到线性扫描真正吃透才发现这道题几乎是一个浓缩的算法方法论。这篇文章我就把这套思考链路完整写下来适合刚接触算法的读者也适合想复习动态规划、准备面试或者写业务代码时遇到类似需求的开发者。1. 先弄明白“最大连续子序列”到底在求什么1.1 问题定义与一个经典例子假设你手里有一个数组 arr长度 n。所谓连续子序列专业叫法是连续子数组subarray它要求选中的元素在原始数组中的下标是连续的不能跳着选。目标是在所有可能的下标区间 [i, j] 中找到 sum(arr[i..j]) 最大的那一个返回这个最大值。如果题目要求同时输出区间还需要额外记录左右端点但绝大多数入门版本只需要返回最大和。用经典数组举例arr [-2, 1, -3, 4, -1, 2, 1, -5, 4]。肉眼扫一遍从下标 3 到下标 6 的区间是 [4, -1, 2, 1]和为 6这是整个数组所有连续区间里最大的和。注意看区间里有一个负数 -1但依然要把它包含进去因为它前后的 4、2、1 加起来的增益不仅能抵消这个负值还有富余。这个直觉其实很关键负数不一定意味着要“断开”关键看它后面接的正数能不能挽回局面。为了把边界定义清楚这里统一采用最常见的约定子数组非空也就是至少要包含一个元素。如果没有这个约定很多解法在“全负数数组”上会得到错误答案 0因为空区间和是 0比任何负数都大。非空这个约定是所有后续推导的基石。1.2 三类边界情况必须提前说清楚第一类数组全部为负数。比如 [-5, -2, -3]最大连续子序列和是 -2也就是最大的那个单独元素。注意这里不是 0因为不允许选空区间。很多初学者在这里翻车写出的代码初始化 best 0遇到全负数组直接输出 0看着好像合理实际完全错误。第二类数组全部为正数。此时最优解一定是整个数组本身因为任何截断都会丢失正数增益。比如 [1, 2, 3]最大和就是 6。如果你写的算法在这个输入上结果小于 6那大概率是状态重置逻辑出了问题。第三类输入数组为空或者长度为 0。经典题一般不允许空输入但实际工程里你一定会遇到。我的习惯是在函数入口做防御数组为 null 直接抛异常长度为 0 返回 0并在注释里写清楚约定。这个细节看起来小对接真实业务时能省掉很多沟通成本。1.3 为什么这道题值得单独拆开讲因为它几乎是一道“算法思想展柜”。暴力枚举是穷举思想分治是分而治之思想线性扫描是动态规划最朴素的形态。同一道题用三种不同复杂度的思路做下来你能直观感受到“算法优化到底优化掉了什么”暴力法的重复计算在哪里分治是怎么利用区间合并信息的线性扫描又是如何把每个子问题的答案滚动递推下去的。这个理解迁移到字符串、树、图等其他问题上一样管用。另外它也是技术面试里出现频率很高的考题。我作为面试官看过太多候选人一上来就默写一个循环被问到“你这个代码为什么能保证正确”就答不上来。能讲清楚状态定义和转移逻辑的人在业务里做性能优化往往也更靠谱因为这类问题考察的本质是从重复计算中找到避免重复的模式。2. 暴力解法先能跑再谈优化2.1 三重循环穷举最直观的写法先别管效率把问题用最直白的方式翻译成代码枚举所有可能的左端点 i枚举所有可能的右端点 j然后对区间 [i, j] 从头到尾求和。写成 Java 大致是这样public int maxSubArray(int[] arr) { int n arr.length; int best arr[0]; for (int i 0; i n; i) { for (int j i; j n; j) { int sum 0; for (int k i; k j; k) { sum arr[k]; } best Math.max(best, sum); } } return best; }这个代码逻辑没有任何问题n 很小的时候用手算也验证得出来。但复杂度一眼就能看出来外层 i 有 n 种选择内层 j 也有大约 n 种选择最内层 k 还要跑区间长度级别的循环三个变量叠加最坏情况是 O(n^3)。当 n 达到一万时这个算法在普通机器上要跑很久完全没法用。2.2 二重循环利用区间扩展省掉一层三重循环慢就慢在最内层求和为什么要重新从 i 加到 j如果已经算过区间 [i, j-1] 的和那区间 [i, j] 的和只需要再加一个 arr[j]。于是可以在枚举左端点 i 以后用另一个指针 j 不断向右移动沿途把 sum 累加一边累加一边更新 best。这样枚举右端点本身就在做求和最内层循环直接消失public int maxSubArray(int[] arr) { int n arr.length; int best arr[0]; for (int i 0; i n; i) { int sum 0; for (int j i; j n; j) { sum arr[j]; best Math.max(best, sum); } } return best; }这个版本复杂度降到 O(n^2)代码也清爽很多。不过 O(n^2) 仍然不够当 n 达到十万级别十亿次求和依然会让程序卡顿。但先别急着否定它暴力二重循环有一个巨大价值它是后面所有优化算法的“标准答案”用来验证更复杂的写法是否正确。我自己做这类题时一定会先用它跑随机对拍测试。2.3 暴力解法的两个关键启发第一个启发任何连续子序列都天然对应一个左端点和右端点所以最终答案必然可以被某个 [i, j] 概括。第二个启发在固定左端点 i 的情况下右端点从 i 走到 n-1 的过程中sum 的变化是“逐步累加”的不需要回到 i 重新扫。这个“从已知状态推未知状态”的视角就是动态规划思想的雏形。顺着这两个启发想下去既然右端点每移动一次都能得到一个以 j 结尾的候选和那能不能不要左端点 i直接只关注“以某个位置结尾的最大和”这样一来问题就从二维区间枚举变成了一维状态递推。别急着跳到第四章先看另一条同样经典的路——分治。3. 分治思路把数组切两半答案只有三种可能3.1 划分问题的三种归属分治法的第一步永远是“假如我已经能解决小一点的问题”。把当前数组从中间 mid 处一分为二那么任何连续子序列要么完全落在左半段要么完全落在右半段要么横跨 mid 两侧。三个候选里取最大就一定得到全局答案。用递归处理左右两半“完全在左半段”就是把左半段数组当成一个全新输入再求一次最大子序列和“完全在右半段”同理。这两个子问题规模各是 n/2递归下去就能算出来。于是整个算法的重心被压到第三个归属上怎么计算“横跨 mid 的最大连续子序列和”。横跨 mid 的区间一定包含 mid 和 mid1 这两个相邻元素而且它的左半部分是从某个点往右一直加到 mid右半部分是从 mid1 往右一直加到某个点。注意不能跨区间跳所以左半部分必须是左半段的一个后缀右半部分必须是右半段的一个前缀。3.2 跨界最大和的计算是分治的精髓我在第一次写分治时最容易错的就是跨界这一块。正确做法是从 mid 出发向左累加中途记录出现过的最大后缀和 leftBest从 mid1 出发向右累加中途记录最大前缀和 rightBest跨界最优就是 leftBest rightBest。这里有一个很容易犯的错误leftBest 必须来自一个连续后缀它不能是“左半段的全局最大子序列”。举例说明左半段是 [5, -2, -3]mid 指向最后一个元素 -3。从 mid 向左累加候选后缀有 -3、-2-3-5、5-2-30最大的是 0可左半段的全局最大子序列是 5也就是单独取第一个元素。如果错误地把 leftBest 当成 5再去加 rightBest 构造跨界和就会拼出一个原数组根本不存在的区间答案自然出错。所以跨界计算必须严格限定在“从 mid 开始向左的连续后缀”。3.3 分治实现的代码与复杂度代价完整实现我写成这样仍然用 Javapublic int maxSubArray(int[] arr) { if (arr null || arr.length 0) { return 0; } return solve(arr, 0, arr.length - 1); } private int solve(int[] arr, int l, int r) { if (l r) { return arr[l]; } int mid (l r) 1; int leftMax solve(arr, l, mid); int rightMax solve(arr, mid 1, r); int leftBest Integer.MIN_VALUE; int sum 0; for (int i mid; i l; i--) { sum arr[i]; leftBest Math.max(leftBest, sum); } int rightBest Integer.MIN_VALUE; sum 0; for (int i mid 1; i r; i) { sum arr[i]; rightBest Math.max(rightBest, sum); } int crossMax leftBest rightBest; return Math.max(Math.max(leftMax, rightMax), crossMax); }复杂度方面递归层数是 log n每一层都要在左右区间做线性扫描总工作量每层是 O(n)所以整体是 O(n log n)。它比暴力解好了太多但还不是最优。分治的价值在于给我们另一种视角跨界区间的组合方式。后面二维最大子矩阵问题里“枚举上下边界后逐列压缩”的思路和这里的跨界合并非常神似。4. 线性扫描法一次遍历解决战斗4.1 状态定义以当前位置结尾的最大子序列和现在回到暴力二重循环给我们的启发。我要枚举的不再是“左端点 右端点”而是一个更聚焦的状态令 dp[i] 表示所有以 i 作为右端点的连续子序列中和最大的那个值。换句话说子序列必须包含 arr[i] 并且以 arr[i] 结尾起点可以是 0 到 i 之间的任意一点。如果能算出每一个 dp[i]最终答案就是所有 dp[i] 里的最大值。问题变成怎么从一个 dp 值推到下一个 dp 值考虑 dp[i] 对应的最优子序列起点有两种可能要么接在 dp[i-1] 那个最优子序列后面要么从 i 位置单独开始。如果 dp[i-1] 大于 0说明接上去对整体有增益最优选择是接反过来如果 dp[i-1] 小于等于 0接上去只会把总和拖低不如直接从 arr[i] 开始。转移方程就是dp[i] max(arr[i], dp[i-1] arr[i])这个方程既简洁又符合直觉。注意这里用“小于等于 0”而不是“小于 0”是因为 dp[i-1] 0 时接上去和不接的和一样既然一样直接取 arr[i] 可以保证子序列更短在某些要求输出区间的变体里更稳。4.2 为什么只需要两个变量滚动前进如果开一个长度为 n 的 dp 数组当然也能算空间是 O(n)。但观察转移方程dp[i] 只依赖 dp[i-1]不依赖 dp[i-2]、dp[i-3]。所以只需要记住“上一个位置的候选值”用一个变量 current 不断滚动更新同时再维护一个变量 best 记录历史所有 dp[i] 的最大值它就是最终答案。public int maxSubArray(int[] arr) { if (arr null || arr.length 0) { return 0; } int current arr[0]; int best arr[0]; for (int i 1; i arr.length; i) { current Math.max(arr[i], current arr[i]); best Math.max(best, current); } return best; }这段代码就是常说的线性扫描法也是一维动态规划的滚动变量写法。很多人第一次看到会惊叹怎么这么短是的最优化结果往往都是短的难点在于理解它为什么正确、边界为什么这样设定。面试时如果只背下来这段被追问两句很容易露馅。4.3 完整走一遍经典数组还是用经典数组 [-2, 1, -3, 4, -1, 2, 1, -5, 4]把每一步的 arr[i]、current 和 best 列出来iarr[i]current max(arr[i], current arr[i])best0-2-2-211max(1, -21) 112-3max(-3, 1-3) -2134max(4, -24) 444-1max(-1, 4-1) 3452max(2, 32) 5561max(1, 51) 667-5max(-5, 6-5) 1684max(4, 14) 56注意 i7 时current 从 6 掉到 1但 best 仍然是 6不会被回退。这正是“历史最优”和“当前位置候选值”分离的意义哪怕后面一路下滑前面那个 6 依然是正确答案。如果只维护一个总最大值却不知道要不要把当前数加上就必须回溯起点算法也就退回 O(n^2) 了。4.4 全局最大值和当前位置候选值必须分开记录我把 current 和 best 的分工再掰开一点。current 回答的是“如果现在必须从某个点出发到 i 为止最长能累积多少”它是一个正在进行的候选best 回答的是“从下标 0 到现在曾经出现过的所有候选里最大的是多少”它是一份归档记录。用生活类比来说current 是你连续打工一段时间后的当前存款best 是你历史上存款的最高峰值。某段时间你可能亏损存款从峰值掉下来但这不影响你曾经达到过峰值的事实。理解了这层关系以后你在纸上手写这段代码会非常稳。我甚至会建议简历里写“熟悉常用算法”的人最好都能当着面试官的面用手势把这个两个变量的角色和转移方程讲清楚。这个算法考察的不是记忆力而是对“重叠子问题”的理解。5. 代码落地写法与典型陷阱5.1 Java、Python、C 三种实现对照同一个算法在不同语言里写出来细节差异值得说一说。Python 版本def max_subarray(arr): if not arr: return 0 current best arr[0] for value in arr[1:]: current max(value, current value) best max(best, current) return bestC 版本int maxSubArray(vectorint nums) { if (nums.empty()) return 0; int current nums[0]; int best nums[0]; for (size_t i 1; i nums.size(); i) { current max(nums[i], current nums[i]); best max(best, current); } return best; }三者在算法上完全等价但有三个容易踩的区别第一Python 里 arr[1:] 会产生一个切片副本如果数组很大内存会多一些在意的话可以改用索引循环第二C 的 max 函数配合 int 没问题但数组元素如果是 long long记得所有中间变量都用 long long第三Java 的 Math.max 和 C 的 std::max 都是函数调用形式Python 的内置 max 也是泛型性能差异在这种 O(n) 算法里可以忽略。5.2 四个高频陷阱初始值、溢出、空数组、空指针第一个陷阱是初始值。很多人的第一版代码会写 int best 0然后边遍历边更新。数组包含正数时没问题但遇到全负数组就直接输出 0错得离谱。正确的初始值应该绑定到 arr[0] 上而不是常数 0。第二个陷阱是整数溢出。如果数组元素很大比如接近 int 上限current arr[i] 可能溢出成负数算法会返回莫名其妙的结果。在常见的在线评测风格题里int 范围内通常安全但真实业务里我建议用 long 做中间变量最后再判断是否能安全收窄到 int。提示判断数组元素规模时不要只看单个数还要看连续区间的累积和。两个各为 20 亿的 int 相加就已经超过 int 上限而这类场景在求和类问题中非常常见。第三个陷阱是空数组。工程函数里 arr 为空时返回 0 还是抛出异常我倾向于在入参校验阶段就明确null 直接抛 IllegalArgumentException长度为 0 返回 0。这样既不会让上层静默吞掉错误又给空数据一个合理结果。第四个陷阱是索引类型。在 C 里如果 nums.size() 是 size_t循环变量却用 int当数组长度超过 int 上限时会出问题虽然现实中很少遇到但写工业级代码要养成用 size_t 的习惯。Java 这边则要注意 n 可能为 0 时怎么取 arr[0]。5.3 用随机对拍测试把实现钉死写了算法之后怎么证明它正确我的做法是写一个简单可靠的暴力 O(n^2) 版本作为基准再用随机生成的小数组反复对比。比如用 Python 这样import random def brute(arr): n len(arr) if n 0: return 0 best arr[0] for i in range(n): s 0 for j in range(i, n): s arr[j] best max(best, s) return best def linear(arr): if not arr: return 0 current best arr[0] for value in arr[1:]: current max(value, current value) best max(best, current) return best for _ in range(10000): arr [random.randint(-100, 100) for _ in range(random.randint(1, 20))] assert brute(arr) linear(arr), arr这种“随机对拍”是我调试算法最常用的方法。它能覆盖到很多手工用例想不到的边界比如连续负数、正负交替、0 值等组合。一旦两个算法输出不一致把触发失败的数组打印出来再手工缩小规模直到找出最小反例最后对照状态定义去推理哪里错了。这个过程比对着答案改代码有效得多。6. 从一维到多维真实业务中的变体与应用6.1 买卖股票的最佳时机差分数组的妙用很多人不知道经典的“只能买卖一次求最大收益”问题其实就是最大子序列和的一层外衣。给定连续 N 天的价格数组 price你只能在某天买入、之后的某天卖出收益就是 price[j] - price[i]其中 j i。把价格数组转成差分数组 diffdiff[k] price[k] - price[k-1]那么从第 i 天买入到第 j 天卖出的总收益 price[j] - price[i]刚好等于 diff[i1] 到 diff[j] 这一段连续和。注意下标偏移差分数组的区间对应原始价格数组的跨天收益。于是问题就变成“在 diff 数组上求最大连续子序列和”。举例[7, 1, 5, 3, 6, 4]差分数组是 [-6, 4, -2, 3, -2]最大连续子序列和为 4 - 2 3 5对应用 1 买入、6 卖出。只要结果大于 0 就有获利空间。唯一的区别是如果所有差分累加结果都是负的股票问题允许“不交易”返回 0因为现实里你可以选择不买。所以我通常在线性扫描结果上再包一层 Math.max(0, result)。这里要小心一个下标细节差分数组长度是 n-1求出的子序列如果跨过了若干个 diff 元素对应的买卖区间天然合法不会出现“卖出日早于买入日”的非法情况因为区间端点是有序的。6.2 二维矩阵的最大子矩阵和降维处理业务里更常见的是二维场景比如一张销售报表的行是门店、列是日期你想找一块连续矩形区域让总和最大。直接在矩阵上做四重边界枚举是 O(n^4)但结合最大子序列和可以把复杂度压到 O(n^2 * m)。核心思路是枚举上下两条边界 top 和 bottom然后把中间每一列的数字压缩成一个元素得到一个长度为列数的一维数组 columnSum。对这个一维数组求最大子序列和就等价于找到“上下边界内、左右连续列区间”的最大子矩阵。伪代码如下def max_submatrix(matrix): rows len(matrix) cols len(matrix[0]) if rows else 0 best -float(inf) for top in range(rows): column_sum [0] * cols for bottom in range(top, rows): for c in range(cols): column_sum[c] matrix[bottom][c] best max(best, max_subarray(column_sum)) return best复杂度从 O(n^4) 降到 O(n^2 * m)。这个“把高维问题压缩成一维数组再套一维算法”的思路是我在实际处理数据透视、窗口聚合报表时常用的招数。它比直接写四重循环优雅很多而且复用一维的测试逻辑正确性更容易保证。6.3 环形数组与最大乘积状态定义的两个进阶方向进阶方向一环形连续子序列。数组首尾相接时最大和可能是跨过边界的。一个经典结论是答案要么等于普通线性最大子序列和要么等于“数组总和减去线性最小子序列和”。后者可以看成在线性序列里挖掉一段连续区间让剩余部分首尾相接被挖掉的部分和最小剩余部分总和自然最大。实现时要注意一个特例如果所有元素都是负数线性最小子序列和等于数组总和减出来的结果是 0但环上非空子序列的最大值其实是最大的那个负数所以要单独判断。进阶方向二最大乘积子数组。求连续子数组的乘积最大值时负负得正让问题不再单调一个很小的负数再乘一个负数可能变成大正数。这时候单个 current 不够要同时维护以 i 结尾的最大乘积和最小乘积两个状态每次用当前元素分别去乘这两个值再取最大和最小。这个变体很好地说明了动态规划的状态定义不是死板的必须根据运算特性调整。我实际做过的一些需求里环形场景出现在监控指标按周循环统计时最大乘积场景出现在计算一组连续运营指标的复合增长率上。它们底层共享同一套“固定尾端点、滚动递推”的 DP 思路只是状态从一个变成两个边界条件各自不同。7. 我的调试心得这类 DP 题怎么避免“背了代码还是错”7.1 一次分治实现翻车的完整复盘有一回我在内部工具里用分治版本求区间最大收益随机对拍时发现某些输入下结果比暴力版本少 1。定位了很久最后发现问题出在跨界最大和的计算上我在算 leftBest 时循环起点写成了 mid - 1没把 mid 本身包含进去。这导致所有跨界区间都默认丢掉了中点元素当最优区间恰好以 mid 开头时答案就偏小。这个错误给我一个很重要的教训分治的“跨界和”必须严格覆盖 mid 和 mid1多一个、少一个都不行。为了以后不再犯我把这个 check 写进对拍测试里而不是只靠肉眼审查。每次修改算法第一件事就是跑随机对拍。对拍测试跑得多了你会发现绝大多数 DP 错误都能归纳成两类状态定义和代码实现不一致或者边界值覆盖不全。7.2 给初学者的最小验证集如果你正在学这个算法我建议不要一上来只看最终代码。先把下面这几个最小用例手推一遍单个元素数组 [5]结果应为 5全负数数组 [-3, -1, -2]结果应为 -1不是 0全正数数组 [1, 2, 3]结果应为 6正负交替且转折点在中段的数组 [1, -2, 3, -4, 5]含 0 值的数组 [0, -1, 0, 2]结果应为 2大数边界 [2147483647, 2147483647]验证溢出处理是否正确把这些用例跑一遍再配合随机对拍基本可以把实现里的低级错误率拉满。算法题最怕的不是不会而是“以为自己会了”用几个刁钻输入去戳它比背诵一百遍原理都管用。最后再分享一个我个人的习惯日常看代码时遇到任何“求一段连续序列的最优值”类需求我都会先画一张“以每个位置结尾”的状态表哪怕是在草稿纸上画。这个动作能让我快速判断这个问题到底适不适合用今天这套 DP 框架也能避免在错误方向上浪费大量时间。