做算法题这些年，我见过最多的一道题不是红黑树，也不是什么冷门数据结构，而是这个：给定一个整数数组，找出一个具有最大和的连续子数组，返回这个最大和。这就是最大连续子序列和算法，很多人也叫它最大子段和问题。我第一次接触它，是在某平台刷题时卡了很久：明明暴力解能跑，却总觉得“应该还有更快的方法”。后来把它从暴力到分治再到线性扫描真正吃透，才发现这道题几乎是一个浓缩的算法方法论。这篇文章我就把这套思考链路完整写下来，适合刚接触算法的读者，也适合想复习动态规划、准备面试，或者写业务代码时遇到类似需求的开发者。

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 和 mid+1 这两个相邻元素，而且它的左半部分是从某个点往右一直加到 mid，右半部分是从 mid+1 往右一直加到某个点。注意不能跨区间跳，所以左半部分必须是左半段的一个后缀，右半部分必须是右半段的一个前缀。

3.2 跨界最大和的计算是分治的精髓

我在第一次写分治时，最容易错的就是跨界这一块。正确做法是：从 mid 出发向左累加，中途记录出现过的最大后缀和 leftBest；从 mid+1 出发向右累加，中途记录最大前缀和 rightBest；跨界最优就是 leftBest + rightBest。

这里有一个很容易犯的错误：leftBest 必须来自一个连续后缀，它不能是“左半段的全局最大子序列”。举例说明，左半段是 [5, -2, -3]，mid 指向最后一个元素 -3。从 mid 向左累加，候选后缀有 -3、-2-3=-5、5-2-3=0，最大的是 0；可左半段的全局最大子序列是 5，也就是单独取第一个元素。如果错误地把 leftBest 当成 5，再去加 rightBest 构造跨界和，就会拼出一个原数组根本不存在的区间，答案自然出错。所以跨界计算必须严格限定在“从 mid 开始向左的连续后缀”。

3.3 分治实现的代码与复杂度代价

完整实现我写成这样，仍然用 Java：

public 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 列出来：

注意 i=7 时，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 best

C++ 版本：

int maxSubArray(vector<int>& 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。

把价格数组转成差分数组 diff，diff[k] = price[k] - price[k-1]，那么从第 i 天买入到第 j 天卖出的总收益 price[j] - price[i]，刚好等于 diff[i+1] 到 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 和 mid+1，多一个、少一个都不行。为了以后不再犯，我把这个 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 框架，也能避免在错误方向上浪费大量时间。