最大连续子序列和全解析：从暴力枚举到Kadane算法

最大连续子序列和这个问题，我估摸着是算法面试里出场率能排进前三的题。题目描述一句话就能说清楚：给定一个整数数组，找出一个连续的子数组，让它的和最大，返回这个最大和。比如经典的测试用例 [-2, 1, -3, 4, -1, 2, 1, -5, 4]，最大连续子序列是 [4, -1, 2, 1]，答案是 6。但你别被这句“简单”骗了，同一个问题从 O(n³) 暴力一路优化到 O(n) 动态规划，中间能拆出四种典型算法，每一种都代表了一类解题范式。这篇我会把四种算法从思路推导、代码实现到复杂度分析全部过一遍，还会补充一些刷题和面试时容易踩的坑，适合正在备战算法面试的开发者，也适合想系统复习基础算法的朋友。

1. 问题定义与暴力枚举法

1.1 先搞清楚题目到底在问什么

拿到这个题，第一件事不是急着写代码，而是把“连续子数组”这个概念抠清楚。子数组必须是原数组中连续的一段，下标连续，元素挨着元素。这和“子序列”是两码事，子序列只需要保持相对顺序，不一定连续。很多人一上来就想着排序、想着找最大元素，方向直接就歪了。

还有一个隐藏约定需要提前确认：空子数组算不算合法？如果题目允许返回空子数组，那答案至少是 0，因为空子数组的和是 0，比任何负数都大。但刷题网站上的经典版本（比如常见的 LeetCode 53 题）默认数组至少有一个元素，要求返回非空子数组的最大和，因此全负数数组的答案应该是最大的那个负数，而不是 0。这个约定直接决定了初始化怎么选，后面会反复提到。

搞清楚这两点，再来看暴力解法就顺理成章了。所有算法题的暴力解都源于同一个朴素念头：把所有可能的情况都列出来，一个个比大小。

1.2 三层循环：最直白的枚举

既然要求连续子数组的最大和，那就枚举所有可能的起点 i 和终点 j，再对区间 [i, j] 求和，最后取最大值。直接翻译成代码就是三层循环。

def max_subarray_sum(nums): n = len(nums) best = float('-inf') for i in range(n): # 起点 for j in range(i, n): # 终点 s = 0 for k in range(i, j + 1): # 累加区间和 s += nums[k] best = max(best, s) return best

这个版本的时间复杂度是 O(n³)，n 稍微大一点，比如 1000，就要跑十亿次级别的加法，基本等于不可用。但我依然建议你把它写一遍，哪怕只是脑内模拟。因为三层循环精确对应了“起点、终点、求和”三个维度，写一遍你对问题空间的理解就落地了。

这里有个新手很容易踩的细节：内层累加的时候，能不能遇到负数就 break？不能。你看着当前累加和变小了，但后面可能跟来一个很大的正数，比如 [-1, 100]，累加到 -1 时直接 break 的话，正确答案 99 就被你扔了。暴力枚举的意义就是穷尽所有可能，任何自以为聪明的剪枝都得先证明不会漏掉最优解才能加。

1.3 去掉一层循环：从 O(n³) 到 O(n²)

三层循环里最蠢的一步是为每个 [i, j] 重新累加区间和。其实从左往右扫一遍，边扫边累加，就能得到所有以 i 为起点、j 不断右移的区间和。这样内层循环就不需要第三层 k 了。

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

代码从三层变两层，本质是“增量计算”：s 保存的是当前区间 [i, j] 的和，j 右移一位，新区间和就是旧的 s 加上 nums[j]，不用从头再加一遍。时间复杂度降到 O(n²)，空间 O(1)。这个思路看着简单，但它是理解前缀和的基础——你其实是在维护“以 i 为起点到当前位置的连续和”，只不过没把中间结果存下来而已。

写代码的时候注意 best 初始值。用 float('-inf') 是最稳妥的，因为不管数组里全是负数还是混着正数，第一次比较都会被某个真实元素覆盖掉。用 0 初始化在全负数组的场景下会直接返回错误的 0。

2. 前缀和：用空间换时间的枚举优化

2.1 前缀和的数学本质

暴力解法的痛点在于区间和每次都要现算。更聪明的做法是预处理一个前缀和数组 prefix，其中 prefix[i] 表示原数组前 i 个元素的和，也就是 nums[0] 到 nums[i-1] 的累加结果。有了 prefix，区间 [i, j] 的和就能用一次减法得到：prefix[j+1] - prefix[i]。

为什么能这么减？你可以把前缀和理解成一个累加器：prefix[j+1] 是前 j+1 个元素的总量，prefix[i] 是前 i 个元素的总量，两者相减，剩下的正好是第 i 到第 j 个元素的总量，一个不多一个不少。就像你记账，月底总额减去月初总额，得到的就是这个月花的钱。

这个概念生活化一点：你站在一条跑道上，每个位置立着一根标尺，标尺上写着从起点到这里的累计距离。想知道任意两点的距离，直接拿两根标尺上的数相减就行，不用重新跑一遍。前缀和干的就是这件事。

2.2 前缀和枚举的实现与复杂度

有了 prefix 数组，枚举所有子数组就变成了枚举所有 i < j 的组合，然后查表相减。

def max_subarray_sum(nums): n = len(nums) prefix = [0] * (n + 1) for i in range(n): prefix[i + 1] = prefix[i] + nums[i] best = float('-inf') for j in range(n + 1): for i in range(j): best = max(best, prefix[j] - prefix[i]) return best

注意 prefix 数组长度是 n+1，prefix[0] = 0，这样区间 [0, j-1] 的和就是 prefix[j] - prefix[0]，不需要单独处理边界。这个细节写代码时很容易漏，漏了就会多出一堆 if 判断。

时间复杂度和优化后的暴力一样，还是 O(n²)，空间 O(n)。你可能觉得前缀和没比暴力快啊？确实，在这个问题里单纯用前缀和并没有突破 O(n²)。但它的价值有两个：一是把“求和”这个操作从 O(n) 降到了 O(1)，二是为更进一步的优化铺路。经典的双指针问题、二维矩阵的子矩阵和，都是前缀和在发挥威力。

2.3 顺着前缀和再走一步：O(n) 解法雏形

前缀和枚举的公式是 max(prefix[j] - prefix[i])，其中 i 严格小于 j。想让这个式子更快，可以换个角度：固定 j，我要找的是它前面最小的 prefix[i]。那只要在遍历过程中维护一个“到当前位置为止见过的最小前缀和”，每次用当前 prefix[j] 减去这个最小值，就能得到以位置 j 结尾的最大子数组和。

def max_subarray_sum(nums): 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

这里有个极其隐蔽的坑：必须先更新 best，再更新 min_prefix。因为 i 必须严格小于 j，也就是说减去的那个最小前缀和必须是当前位置之前的，如果先更新 min_prefix，就会允许空子数组参与比较，全负数组时会错误地返回 0。我当年第一次写这个版本就栽在这里，调试了半天才发现是顺序问题。

这个解法和后面要讲的动态规划殊途同归，本质都是在维护“当前最优”和“历史最优”两个状态。如果面试官让你从暴力讲起，你可以从前缀和这条线一路推到这个 O(n) 解法，他会很满意。

3. 分治法：把问题一分为二的递归美学

3.1 分治的基本框架

分治法的思想很优雅：把数组从中间劈成两半，那么最大连续子序列和只可能出现在三个地方：完全在左半边、完全在右半边、或者横跨中点。前两种情况交给递归解决，第三种情况需要单独计算。

为什么这样划分是完备的？因为任意一个连续子数组，要么不跨中点，要么跨中点，不存在第三种可能。这就好像你把一条绳子从中间剪断，任何一段连续的部分，要么完全在左段，要么完全在右段，要么正好包含了剪口位置。

递归的 base case 很简单：区间只有一个元素时，最大和就是它本身，直接返回。

3.2 跨中点的最大和怎么求

跨中点的最大和，不能通过递归直接得到，需要从中间向两边扩展来扫描。具体做法是：从中点出发，向左累加，记录能得到的最大左半段和；再从中点右边一个位置出发，向右累加，记录能得到的最大右半段和；两者相加就是横跨中点的最大连续子数组和。

这里有个关键点：为什么跨中点的子数组一定要从中点出发向两边扩展，而不是从任意位置跨越？因为任何跨中点的连续子数组，它的左半部分一定是以某个位置结尾、且包含 mid 的连续段，右半部分一定是以 mid+1 开头、且向右连续的段。从 mid 向左扫描能覆盖所有可能的左半段，从 mid+1 向右扫描能覆盖所有可能的右半段，两者组合正好覆盖所有跨中点的子数组。

def max_subarray_sum(nums, left, right): if left == right: return nums[left] mid = (left + right) // 2 left_best = max_subarray_sum(nums, left, mid) right_best = max_subarray_sum(nums, mid + 1, right) # 从 mid 向左扩展的最大和 left_cross = float('-inf') s = 0 for i in range(mid, left - 1, -1): s += nums[i] left_cross = max(left_cross, s) # 从 mid + 1 向右扩展的最大和 right_cross = float('-inf') s = 0 for i in range(mid + 1, right + 1): s += nums[i] right_cross = max(right_cross, s) return max(left_best, right_best, left_cross + right_cross)

调用方式是 max_subarray_sum(nums, 0, len(nums) - 1)，调用前记得处理空数组。这段代码里最容易写错的是两个扫描循环的边界：向左扫描是从 mid 一直走到 left，向右扫描是从 mid+1 一直走到 right，方向不能反，范围不能多。写的时候可以举个具体例子手推一遍，比如对数组 [-2, 1, -3, 4, -1]，mid 是 2，向左扫得到 1（取 nums[2] = -3 时是 -3，取 nums[1]+nums[2] = -2，取 nums[0]+nums[1]+nums[2] = -4，最大是 -2？不对，让我重新算）。

我实际手推一遍：nums = [-2, 1, -3]，mid = 1，left=0, right=2。向左扫：s = nums[1] = 1，left_cross = 1；s = 1 + (-2) = -1，left_cross 保持 1。所以左边跨中点部分是 1。向右扫：s = nums[2] = -3，right_cross = -3。跨中点最大和是 1 - 3 = -2。递归左半边 [-2] 返回 -2，右半边 [-3] 返回 -3，三者取最大是 -2。但看原数组，非空子数组有 [-2]、[1]、[-3]、[-2,1]、[1,-3]、[-2,1,-3]，最大是 1。这里怎么是 -2？问题出在 mid 的选法和扫描逻辑：当数组只有 3 个元素时，mid = 1，跨中点的子数组必须包含 nums[1] 并且跨越到另一边，但真正的最大子数组 [1] 是只包含 mid 本身、没有跨越左右的，它被当作“完全在左半边”？不对，mid 属于左半边还是右半边取决于实现。我的递归把 mid 归给了左半边，left_best 只计算 [left, mid] 即 [-2, 1] 的最大值，递归返回 max(nums[0], nums[1], nums[0]+nums[1]) = 1。所以最终 max(-2, -3, 1) - 这里应该是 max(left_best=1, right_best=-3, cross=-2) = 1。对啊，刚才我说递归左半边 [-2] 是不对的，因为递归左半边的区间是 left 到 mid，即 [-2, 1] 而不是 [-2]。所以结果是 1，正确。我自己差点把自己绕进去，这也说明手推一遍确实有必要。

3.3 复杂度分析与适用价值

分治法的递推关系是 T(n) = 2T(n/2) + O(n)，其中 O(n) 来自两次向两边扩展的扫描。解这个递推式，时间复杂度是 O(n log n)。空间复杂度是递归调用栈的深度 O(log n)。

实测中，O(n log n) 在这个问题上肯定不如 O(n) 的解法，但分治法并不是没有价值。它提供了一套很好的并行化思路：左右两半可以完全独立地递归计算，只有跨中点部分需要合并，在并发场景下可以把大规模数组切分成多个块并行处理。另外，分治法的“跨中点合并”技巧在很多其他问题里都有应用，比如求最大乘积子数组的某些变体、或者归并排序类的题目。掌握这个思路比死记这一题更有意义。

4. 动态规划：O(n) 的 Kadane 算法

4.1 状态定义与转移方程

动态规划的解法是这个问题的天花板，也是面试官最想看到的最终答案。它的核心不是盯着“全局最大和”看，而是转换思路：定义 dp[i] 为“以第 i 个元素结尾的连续子数组的最大和”。注意，这里强制要求子数组包含 nums[i]，子数组的右端点必须是 i。

那么 dp[i] 怎么从前面的状态推出来？对于以 i 结尾的子数组，无非两种情况：要么把 nums[i] 接到以 i-1 结尾的最优子数组后面，要么甩开前面所有元素，从 nums[i] 自己开始。用公式写就是：

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

最终答案就是所有 dp[i] 里的最大值。为什么答案一定藏在“以某个位置结尾”的状态里？因为任何子数组都有右端点，它对应的“以右端点结尾的最大和”至少不比它小，所以全局最优一定在某个 dp[i] 中取到。

这个转移为什么完备？因为“通过 i-1”是把所有历史信息浓缩成 dp[i-1] 这一个数，它不关心你具体从哪个位置开始，只关心以 i-1 结尾能拿到的最大和是多少。这体现了动态规划里“无后效性”的概念：未来的决策只依赖当前状态，不依赖达到这个状态的具体路径。这句话听起来玄乎，但代码写出来极其简单。

4.2 代码实现与滚动变量优化

先写一个用 dp 数组的版本，逻辑清晰，方便理解：

def max_subarray_sum(nums): if not nums: return 0 # 或根据约定抛出异常 dp = [0] * len(nums) dp[0] = nums[0] best = dp[0] for i in range(1, len(nums)): dp[i] = max(nums[i], dp[i - 1] + nums[i]) best = max(best, dp[i]) return best

观察这个转移方程，dp[i] 只依赖 dp[i-1]，前面的状态用完即弃，完全可以用一个变量滚动维护，把空间从 O(n) 压到 O(1)。这就是常说的 Kadane 算法：

def max_subarray_sum(nums): if not nums: return 0 cur = 0 best = float('-inf') for x in nums: cur = max(x, cur + x) best = max(best, cur) return best

我第一次看到这个版本的时候，觉得简单得不像话，甚至怀疑是不是漏了什么。但仔细推一遍全负数组 [-5, -2, -3]：cur 从 0 开始，第一个元素后 cur = max(-5, -5) = -5，best = -5；第二个元素后 cur = max(-2, -7) = -2，best = -2；第三个元素后 cur = max(-3, -5) = -3，best 保持 -2。答案 -2，正确。关键就是 best 初始化为负无穷，cur 会自然地在“延续旧状态”和“重新开始”之间做选择。

注意别把 cur 初始化成 0 以后还要拿它和 0 比，那是允许空子数组的写法。这里 cur = max(x, cur + x) 已经强制要求非空了，因为两个候选都包含 x。

4.3 变体一：不只返回最大和，还要返回子数组本身

面试官经常追加一问：光返回最大和不够，你把这个子数组的起止下标也给我。这个变体考的是对状态转移的理解是否到位。只需要在 cur 决定“重新开始”和“延续”的时候，更新起点即可。

def max_subarray_with_indices(nums): if not nums: return 0, -1, -1 cur = 0 best = float('-inf') start = end = 0 temp_start = 0 for i, x in enumerate(nums): if x > cur + x: # 重新开始更优 temp_start = i cur = x else: # 延续旧状态更优 cur = cur + x if cur > best: best = cur start = temp_start end = i return best, start, end

这里的判断条件 x > cur + x 等价于 cur < 0，也就是说前面的子数组和已经是负数，拖后腿了，不如扔掉。这个“扔掉负前缀”的角度非常直观：当前面的累计和为负时，它只会让后续的和变小，保留它没有任何好处。很多人理解 Kadane 算法就是从这个角度切入的。

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

一维会做了，面试官还可能把问题升级成二维：给定一个 m 行 n 列的矩阵，找一个子矩阵，使得子矩阵内所有元素的和最大。这个变体是一维 Kadane 的最经典延伸。

核心思路是枚举行上边界 top 和下边界 bottom，把上下边界之间的每一列元素纵向相加，压缩成一个长度为 n 的一维数组，再对压缩结果跑一遍 Kadane。为什么要这么压缩？因为选定上下边界后，一个子矩阵的和等于它每一列元素和的总和，而列和压缩成一维数组后，问题就变成了求这个一维数组的最大连续子数组和，列与列之间恰好对应子数组的连续段。

def max_submatrix_sum(matrix): if not matrix or not matrix[0]: return 0 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, kadane(col_sum)) return best

复杂度是 O(m²n)，适合行列规模不极端的场景。这个题的难点不在于 Kadane 本身，而在于“压缩列”这一步抽象。面试时能主动提出“把二维问题降到一维再复用 Kadane”，通常就是加分项。

5. 四种算法对比与工程选型

5.1 复杂度与思路对照

四种算法放在一起看，脉络非常清晰。我用一个表把关键信息整理出来：

别小看这张表，面试官让你分析四种算法时，能脱口说出复杂度递进关系，比背十个模板都管用。我面试别人的时候，最想看到的不是直接背出 Kadane，而是从暴力开始一步步推导，讲清楚每一步优化解决了什么瓶颈。这个过程比结果更体现算法素养。

5.2 工程上怎么选

实际业务里，直接处理一维数组最大连续子数组和的场景不算多，但它的变形无处不在：股票价格的最大单次买卖收益、信号数据的峰值区间检测、日志流中某类指标的最优观察窗口，底层都能抽象成这个问题。

数据规模是选型的第一决定因素。几百个元素的数组用 O(n²) 完全没问题，实现简单、不易出错；但如果数据是千万级甚至实时流式数据，O(n) 的 Kadane 就是唯一合理的选项，它不仅能处理数组，还能做到流式在线计算——来一个元素更新一次状态，不需要保存整个历史数据。

分治法在工程中反而用得少，除非你的数据天然分布在不同节点上，需要分布式归并结果。这时候每个节点算自己那部分的最大子段和、跨边界的那个后缀前缀和，再把结果汇总，思路和分治法完全一致，只不过“递归”换成了“分布式通信”。理解了分治法的三种情况合并，你就能设计这种分布式版本。

6. 常见问题与避坑实录

6.1 边界条件检查清单

这题的边界条件比绝大多数算法题都刁钻。我列一个自己平时写代码前必检查的清单：

• 空数组：直接返回 0 还是抛出异常？取决于约定，但必须显式处理，不能让它进入主逻辑。
• 单元素数组：返回元素本身，无论正负。
• 全负数数组：返回最大的负数，不是 0。这是最容易错的一个点，根源在于空子数组是否合法的约定。
• 全正数数组：整个数组的和就是答案，Kadane 会自然累加全部元素，不会触发“重新开始”的分支。
• 首尾元素参与：最优子数组可能恰好从第 0 个元素开始、到最后一个元素结束，检查初始化条件是否让这两种情况被漏掉。

6.2 面试和笔试中的三大坑

第一个坑是读题不仔细。题目问的是“返回最大和”还是“返回子数组”，这两个答案的形态完全不一样。返回子数组意味着要维护起止下标，代码复杂度会高一个档次。

第二个坑是索引约定。刷题网站的输入输出五花八门，有的要求返回（start, end）区间，区间左闭右开还是左闭右闭，直接看例子判断。我见过太多人在这个细节上丢了分，代码逻辑全对，就卡在边界返回上。

第三个坑是忽略了“连续”这个限定词。有的人一看到“最大和”，脑子一热就按排序或者贪心找最大正数去做，完全忘记了子数组必须连续。连续是这个问题的灵魂，所有算法的设计都是围绕连续性展开的。

6.3 相关变体题的自检清单

遇到下面这些变体，你可以拿它们检验自己是不是真懂了这个问题的本质：

• 环形数组的最大子数组和：处理思路是先求常规最大子段和，再求最小子段和，答案取两者中较大。难点在于理解“跨过边界”等价于“总数减去中间的最小段”。
• 买卖股票的最佳时机（一次交易）：本质是求两个元素的最大差值，可以转化成前缀最小值和当前值的比较，和前缀和思路同源。
• 最大乘积子数组：状态转移里多了正负号的制约，需要同时维护最大乘积和最小乘积两个状态，考的就是对“连续性状态压缩”的理解深度。

我自己带过不少人刷题，发现能把这四种算法和两三个变体讲清楚的，基本都不会被这类题卡住。关键在于不要背代码，而是理解每种算法“为什么能这么想”：暴力是穷举所有方案，前缀和是空间换时间，分治是化整为零再合并，动态规划是提取最优子结构。四种思路恰好是算法设计的四个基本功，这一个题全练到了，性价比非常高。

最后再分享一个小技巧：学这类经典算法题的时候，我习惯把复杂度分析写在代码注释的第一行。比如 # O(n) / O(1)。面试官翻到你的代码，第一眼看到的就是你对自己方案的复杂度有清醒认识。这比把代码写得花哨有用得多。