最大连续子序列和这个问题我估摸着是算法面试里出场率能排进前三的题。题目描述一句话就能说清楚给定一个整数数组找出一个连续的子数组让它的和最大返回这个最大和。比如经典的测试用例 [-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[j1] - prefix[i]。为什么能这么减你可以把前缀和理解成一个累加器prefix[j1] 是前 j1 个元素的总量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 数组长度是 n1prefix[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 的连续段右半部分一定是以 mid1 开头、且向右连续的段。从 mid 向左扫描能覆盖所有可能的左半段从 mid1 向右扫描能覆盖所有可能的右半段两者组合正好覆盖所有跨中点的子数组。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向右扫描是从 mid1 一直走到 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 1left0, right2。向左扫s nums[1] 1left_cross 1s 1 (-2) -1left_cross 保持 1。所以左边跨中点部分是 1。向右扫s nums[2] -3right_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_best1, 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) -5best -5第二个元素后 cur max(-2, -7) -2best -2第三个元素后 cur max(-3, -5) -3best 保持 -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 复杂度与思路对照四种算法放在一起看脉络非常清晰。我用一个表把关键信息整理出来算法时间复杂度空间复杂度核心思路适用场景暴力枚举三层循环O(n³)O(1)枚举所有起点、终点并逐段求和仅用于理解问题n 极小50暴力优化两层循环O(n²)O(1)枚举起点边移动终点边累加区间和n 小于几千的简单场景前缀和枚举O(n²)O(n)预处理前缀和O(1) 查询区间和需要频繁查询区间和的场景分治法O(n log n)O(log n)递归分左右跨中点合并并行计算场景算法课堂演示动态规划KadaneO(n)O(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)。面试官翻到你的代码第一眼看到的就是你对自己方案的复杂度有清醒认识。这比把代码写得花哨有用得多。
