最大序列和详解：从Kadane算法到五种变体与面试避坑指南

1. 破题：最大序列和到底在问什么

“3393. 最大序列和”这个题号，大概率来自某个算法题库或线上练习平台的题目编号，但真正值钱的不是编号本身，而是“最大序列和”这五个字背后的那个经典问题：在一个整数数组里，找出一段连续的子序列，让它的累加和最大。

先说人话版本。假设你手里有一串数字：

[-2, 1, -3, 4, -1, 2, 1, -5, 4]

肉眼扫一遍，最大的连续子段是从下标3到下标6，也就是[4, -1, 2, 1]，累加和是6。这就是最大序列和的标准答案。如果允许选择空子序列，那空子序列的和是0，问题就变成了“最大子数组和，允许为空”；如果要求必须选至少一个元素，就是经典的“最大子数组和，不允许为空”。这两个版本在LeetCode上分别对应53题的两种问法，很多初学者在边界条件上栽跟头，就是没搞明白题目到底允不允许选空段。

这个问题之所以被反复拿出来考，不是因为它难，而是因为它同时覆盖了三个核心能力点：

• 建模能力：把“连续子序列的最大和”翻译成一个可以用递推关系表达的数学问题。
• 优化意识：暴力解法谁都能写，但要在O(n)时间、O(1)空间内解决，需要真正理解动态规划的状态压缩。
• 边界敏感度：全负数数组、全零数组、单元素数组、最大和出现在数组两端等情况，都是测试用例里最爱埋雷的地方。

我第一次认真研究这道题是在准备面试的时候。当时刷题平台把这题标成“简单”，结果我身边好几个同事在讨论“为什么这题是简单难度”时，能把判断条件写错——有人直接用了前缀和的暴力两重循环，有人写DP但没处理好负数开局的情况。这篇文章就把这题的原理、推导、代码、变形全部摊开讲清楚，适合刚入门动态规划的读者，也适合想把这个经典题目彻底吃透准备面试的人。

2. 从暴力解法开始：为什么两重循环是“正确但没用”的

先说结论：最大序列和没有捷径可走之前，把每个可能的连续子段都算一遍，是最直观也最不可能错的思路。

2.1 三重循环的“傻瓜版本”

最朴素的版本是枚举起点i和终点j，然后把这个区间里的所有元素加起来求和：

def max_subarray_bruteforce(nums): n = len(nums) best = float("-inf") for i in range(n): for j in range(i, n): total = 0 for k in range(i, j + 1): total += nums[k] best = max(best, total) return best

这个版本的时间复杂度是O(n³)，对30个元素的数组都跑得有点慢。它的价值在于定义清晰：“我就是枚举所有可能的连续区间，算出每个区间的和，再取最大值”。这个逻辑完全照着题目字面意思来，不会出错。

2.2 两重循环：省掉一层累加

稍微优化一点，保留起点枚举，但每加一个元素就更新一次当前区间和，省掉第三层循环：

def max_subarray_better(nums): n = len(nums) best = float("-inf") for i in range(n): current = 0 for j in range(i, n): current += nums[j] best = max(best, current) return best

这个写法的时间复杂度降到O(n²)，对于一个长度为10万的数组来说，大约需要100亿次加法运算，仍然不可接受。

2.3 暴力法的真正价值不在“跑得快”，而在“验得对”

我自己在实际做题时的习惯是：先用最暴力的写法做一个基准函数，再用它和新学的高效算法做对拍——也就是随机生成大量数组，把两个函数的输出结果逐一对比。这样能快速验证高效算法是否存在边界case处理错误。

举个具体例子，当年我用Kadane算法（就是下一节要讲的O(n)解法）写完之后，工程师同事提醒我注意一个场景：当数组全为负数时，best的初始值如果设成0就会出问题，因为它会返回0而不是最大的那个负数。我用暴力的两重循环对拍了一轮，立刻发现了这个bug。所以暴力解法虽然不能直接用于线上大数据，但它作为“测试基准”的价值非常大。

2.4 复杂度不是“差不多”，而是量级差异

很多人觉得O(n²)和O(n)差别不大，这是典型的感觉偏差。我用一组实际数据做过对比：

这张表是我在本地用Python环境大概测出来的，具体数值会因机器性能浮动，但量级关系是一致的：O(n²)在10万量级就已经卡到用户无法接受的程度，而O(n)几乎是一瞬间。这也是为什么面试官几乎不会接受一个O(n²)的最大子数组和方案——不是不能运行，而是这个方案的扩展性决定了它只能算玩具。

3. 核心推导：Kadane算法是怎么一步步想出来的

最大序列和的标准高效解法叫Kadane算法，时间复杂度O(n)，空间复杂度O(1)。背代码很容易，但如果不理解它为什么对，稍微换个问法你就可能写错。

3.1 从一个朴素的问题开始：每个位置能提供的新子段

假设我们已经计算出了以nums[i-1]结尾的子数组的最大和，记为dp[i-1]。现在我们站在nums[i]面前，需要决定：把nums[i]续接到前面的某个子段尾端，还是让它单独开一个新段？

这个“二选一”的决策，就是整个算法的灵魂。

如果dp[i-1] + nums[i] > nums[i]，说明前面那段拖累得不够多，续上去更划算；如果dp[i-1] + nums[i] < nums[i]，说明前面的最大和反而是一个负数大坑，继续接着它只会让总和小下去，果断把它甩掉，从当前位置重新开始。

用数学语言翻译就是：

dp[i] = max(nums[i], dp[i-1] + nums[i])

这个式子就是状态转移方程。理解这个方程，比背代码重要一百倍。

3.2 “前一段最大和是负数时必须断开”的直觉验证

我用一个例子来验证这个决策的合理性。考虑数组：

[-2, 1, -3, 4]

• dp[0] = -2（以nums[0]结尾的最大和，只能选它自己）
• dp[1] = max(1, -2 + 1) = max(1, -1) = 1。这里决策是“从位置1重新开始”，因为前面的最大和是-2，是负贡献。
• dp[2] = max(-3, 1 + (-3)) = max(-3, -2) = -2。这里续接了前面的“1”，因为-3本身更小。
• dp[3] = max(4, -2 + 4) = 4。前面最高也就-2，是负的，续接不如新建。

最后答案就是所有dp[i]的最大值：max(-2, 1, -2, 4) = 4。

这个例子直观地展示了为什么选择“重新开始”是合理的——假如我们不判断dp[i-1]的正负，而是把每个元素都硬塞进同一个子段里，那么在整个数组上算出来的就是总和，显然不是最大连续子段和。

3.3 为什么要记录一个“全局最大值”而不是只看dp数组末尾

另一处容易忽略的点是：答案不一定以最后一个元素结尾。最大和子段的结尾索引可以出现在数组的任意位置。

比如数组：

[5, -10, 6, 6]

• dp[0] = 5
• dp[1] = max(-10, 5 - 10) = -5
• dp[2] = max(6, -5 + 6) = 6
• dp[3] = max(6, 6 + 6) = 12

dp[1]是-5，dp[3]是12，答案是12。这里没问题。但如果数组在中间就已经达到最大值，比如：

[8, -1, -1, -1, 9]

• dp[0] = 8
• dp[1] = 7
• dp[2] = 6
• dp[3] = 5
• dp[4] = 14

最后答案落在末尾，没问题。再看另一个例子：

[10, -1, -1, -1, -1]

dp[0]=10，之后一路递减，dp[4]=6。如果只返回dp[n-1]，答案是6，显然错了，正确是10。所以必须维护一个best_so_far = max(best_so_far, dp[i])，不断同步更新。

3.4 空间压缩：从dp数组到两个变量

完整版本的DP代码会开一个长度为n的dp数组，空间复杂度O(n)。但观察转移方程可以发现，dp[i]只依赖dp[i-1]，和更早的状态没有任何关系，所以完全可以用一个变量滚动维护：

def max_subarray_kadane(nums): best = float("-inf") current = 0 # 等价于 dp[i-1] for x in nums: # current + x 可能小于 x，说明前面那段是负贡献，直接断开 current = max(x, current + x) best = max(best, current) return best

这段代码就是Kadane算法的完整实现，核心逻辑一共三行。current表示以当前元素结尾的最大子段和，best记录历史最大值。每一步的语义和前面的dp[i]完全一致，只是空间上不再保留所有历史状态。

3.5 和“前缀和取最小”之间的关系

还有一个常见的等价解法：先算前缀和数组prefix[i] = sum(nums[0:i])，那么子段和sum(nums[i:j]) = prefix[j] - prefix[i]。想让子段和最大，就是要prefix[j] - min(prefix[0..j-1])最大，所以一边扫描前缀和，一边记录历史最小值即可：

def max_subarray_prefix(nums): prefix = 0 min_prefix = 0 # 允许选择空子序列时，min_prefix初始为0 best = float("-inf") for x in nums: prefix += x best = max(best, prefix - min_prefix) min_prefix = min(min_prefix, prefix) return best

这个写法和Kadane本质上是同一件事的两种视角。面试时如果能把这个关系讲明白，通常会给面试官留下“真懂”的印象，因为很多人只会背Kadane，却不知道它和前缀和的联系。

3.6 如果题目允许选择空子序列，怎么改

LeetCode 53是不允许选空的，所以best初始值要设为float("-inf")，保证至少选一个元素。但有些变体题目（比如求最大子数组和且允许返回0），则把best初始化为0即可。这两种情况我都在实际刷题时见过，务必看清楚题目条件再动笔。

4. 变体与扩展：一个题，五个坑

最大序列和真正的价值，体现在它衍生出来的一堆变体里。每个变体都在原题基础上加了个小限制，解法却经常需要重新思考。

4.1 变体一：环状数组的最大子数组和

题目给一个首尾相连的环形数组，问最大连续子段和能有多大。暴力做法是把数组展开成两倍长度枚举，但更优雅的思路是转化。

关键观察：环状数组的最大子数组只有两种情况——要么是普通线性数组里的一个子段，要么跨越了环的边界。跨越边界时，等价于“总和减去数组内部最小子段和”：

max_circular = max(linear_max, total_sum - linear_min)

其中linear_min就是“最小子数组和”，用Kadane对称的写法算出来即可。但这里有一个隐藏陷阱：如果整个数组全是负数，total_sum - linear_min会变成0（因为linear_min = total_sum），而正确答案应该是最小的那个负数，不能选空段。处理方式是判断linear_max < 0时直接返回linear_max。

def max_subarray_circular(nums): def kadane_min_or_max(nums, find_min=False): best = float("inf") if find_min else float("-inf") cur = 0 for x in nums: cur = min(x, cur + x) if find_min else max(x, cur + x) best = min(best, cur) if find_min else max(best, cur) return best linear_max = kadane_min_or_max(nums, find_min=False) if linear_max < 0: return linear_max total = sum(nums) linear_min = kadane_min_or_max(nums, find_min=True) return max(linear_max, total - linear_min)

这个变体在LeetCode上是912还是919系列记不太清了，反正是中等题，理解了转化思路就没什么难度。

4.2 变体二：二维矩阵的最大子矩阵和

把一维数组升级成二维矩阵，要找到一个子矩阵（连续行、连续列），让矩阵内元素和最大。

解法是把多行压成一行。固定子矩阵的上下边界为第i行和第j行，然后对每一列求和，得到一个长度为列数的一维数组，再在这个一维数组上跑Kadane。核心代码如下：

def max_submatrix(matrix): rows, cols = len(matrix), len(matrix[0]) best = float("-inf") for top in range(rows): col_sum = [0] * cols for bottom in range(top, rows): for c in range(cols): col_sum[c] += matrix[bottom][c] best = max(best, max_subarray_kadane(col_sum)) return best

复杂度O(n³)，其中n是较大维度。这个变体在面试中出现频率很高，因为它综合考察了枚举思维和动态规划功底。

4.3 变体三：最大乘积子数组

子数组和变成子数组乘积，看起来只换了一个运算符，难度完全不在一个量级，因为负数乘负数会变正数，导致“局部最大值”和“局部最小值”会相互转化。

状态转移需要同时维护两个值：

def max_product_subarray(nums): cur_max = cur_min = best = nums[0] for x in nums[1:]: if x < 0: cur_max, cur_min = cur_min, cur_max cur_max = max(x, cur_max * x) cur_min = min(x, cur_min * x) best = max(best, cur_max) return best

这个变体让我深刻体会到，Kadane算法不只是“求最大和的算法”，更是一个“以当前元素结尾的最优状态递推”的框架。理解了这个框架，遇到任何“连续子数组的xxx”类问题都更容易上手。

4.4 变体四：限定了子数组长度的最大序列和

题目要求子数组长度不能超过K。这时简单Kadane就不够用了，因为可能某一步的最优解是“以i结尾、长度为K+1”的更长子段，但题目不允许跨过长度限制。

标准解法是滑动窗口 + 前缀和，窗口长度上限为K。枚举右端点固定时，就是要最小化窗口左端点的前缀和，而这个最小值一定出现在“离当前位置距离小于等于K”的范围内，所以需要一个双端队列（deque）维护单调递增的前缀和下标：

from collections import deque def max_subarray_limited(nums, k): prefix = [0] for x in nums: prefix.append(prefix[-1] + x) dq = deque([0]) best = float("-inf") for i in range(1, len(nums) + 1): while dq and dq[0] < i - k: dq.popleft() best = max(best, prefix[i] - prefix[dq[0]]) while dq and prefix[dq[-1]] >= prefix[i]: dq.pop() dq.append(i) return best

这段代码的思路是用单调队列维护“可选的最小前缀和下标”。如果对单调队列不熟，把它想象成每次都在一个长度为K的滑窗里找最小值，就很好懂了。

4.5 变体五：需要返回具体子数组的下标区间

面试里经常追问：“不仅要返回最大和，还需要返回对应的起始和结束下标。”这时Kadane算法需要额外记录两层信息——当前子段的起始位置，以及最优解对应的起始位置：

def max_subarray_with_indices(nums): best = float("-inf") cur = 0 best_start = best_end = 0 cur_start = 0 for i, x in enumerate(nums): if cur + x > x: cur = cur + x else: cur = x cur_start = i if cur > best: best = cur best_start = cur_start best_end = i return best, best_start, best_end

注意这里判断条件从max(x, cur + x)改成了if cur + x > x，目的是明确知道什么时候发生了“重新开始”，从而追踪子段的起点。如果cur + x == x，说明前面那段和为0，一般视题目要求决定是否保留。

这个追踪下标的版本，是我在实际工作中真正用得最多的。因为算法题里的最大序列和，落到现实场景往往是“找出哪一段时间窗口内的指标异常偏高”，只告诉一个数值而不告诉位置，基本等于白算。

5. 从面试到实战：那些容易翻车的细节和我的习惯

磕磕绊绊写了这么多变体之后，我想把几个真正让我翻过车、也让我后来形成固定习惯的细节单独拎出来讲讲。

5.1best的初始值到底怎么定

如果题目要求至少选一个元素，best初始值要用float("-inf")，用0会导致全负数数组返回0，这是错的。如果题目允许选择空子序列（返回0），初始值设0也OK。我在LeetCode 53上吃过这个亏，在全负数用例上提交失败，检查半天才发现是初始值问题。

5.2 整数溢出问题

Python不存在整数溢出，但如果你用C++或Java写这题，cur + x可能溢出。面试现场如果被问到long long不够用怎么办，标准答案是用更宽的类型（比如__int128或BigInteger），或者结合题目给出的数值范围分析是否需要用贪心策略替代直接累加。实际竞赛里数组长度十万、元素值到达10^9时，最大和可能是10^14，32位int必然溢出，一定要用64位。

5.3 对比测试是我最有安全感的习惯

前面提过，我自己做题一定先写暴力版本做基准，再写最优解，然后随机生成大量测试数据对拍。这个习惯看起来费时间，但长期下来帮助特别大，尤其是刷变体题的时候。有一次写环形数组变体，暴力版本和优化版本对拍出数百组随机数据后完全一致，我才敢提交。那些“感觉没问题就交”的冲动，往往都换来了一两次WA。

5.4 代码风格值得注意的点

Kadane算法本身极短，但短代码更容易出现不可读的写法。我的习惯是变量名直接表达语义：best表示全局最优，cur表示以当前元素结尾的最优。写成max_ending_here和max_so_far也可以，但不要用a、b这类无意义命名。面试时更建议写成带有明确语义的长名字，因为面试官要的不是你写得有多精炼，而是希望确认你理解你在写什么。

6. 如果让我重新讲一遍最大序列和

讲了这么多，最后我想倒过来，用最口语的方式把这题再串一遍。

最大序列和本质上是在问：在一个数组里，哪一段连续的数字能加出最大和。你不要一上来就想着“怎么算最大段”，而是先想“以每一个位置结尾的段，最好能是多少”。如果站在第i个数字面前，只有两种选择——把当前数字接到前一个最优段的尾巴上，或者丢弃前面的所有内容，让当前数字自己开一个新段。哪个更大，就选哪个。每个位置都比一次，顺便记录历史最大值，答案就出来了。

这个思想叫做最优子结构，是动态规划最核心的直觉。刚开始接触DP的人会觉得绕，但我可以给一个生活类比：你在路上收集果子，走到某个点发现背的筐子实在太重，里面装的全是烂果子，那最理性的选择就是把筐子扔了，只拿眼前这个果子重新开始；如果筐子里的果子还是好的，背着继续走总比自己单独拿一个更划算。每走一步都做一次“扔掉重来还是继续背着”的判断，最后总收获最多的那个走法，就是答案。

最后分享一个我的小习惯：每次学一个经典算法，我都会强迫自己用三种方式写一遍，暴力版、标准版、变体版，并且故意写错一两个地方（比如把max(nums[i], cur + nums[i])写成cur + nums[i]），然后让测试用例替我纠正。这个过程比自己反复看十遍代码更有效。最大序列和只是其中一个例子，但这个“从暴力到最优、从一维到变体、从背代码到讲直觉”的学习路径，是我认为学任何算法题都值得复制的通用方法。