1. 先搞清楚问题最大连续子序列和到底在求什么1.1 一句话定义和例子最大连续子序列和英文叫 Maximum Subarray Sum是算法学习里一个绕不开的经典问题。给你一个整数数组让你找出一段连续的子数组使得这段子数组的和最大最后返回这个最大和。注意“连续”两个字它是整道题的核心约束也是很多人一开始理解偏掉的地方。我习惯用生活中的例子来拆解。假设你记录了某只股票连续十天的每日盈亏正数代表当天赚了负数代表当天亏了。你想找一个连续的时间窗口让这一整段的累计盈亏最大这就是最大连续子序列和。它和“随便挑几天组合起来的最大收益”是不同的因为你的选择必须是一条连续的区间不能跳着来。看一个标准例子数组[-2, 1, -3, 4, -1, 2, 1, -5, 4]。肉眼扫一下所有连续子数组里面[4, -1, 2, 1]这一段的累加和是4 (-1) 2 1 6没有其他连续区间的和比 6 更大所以答案就是 6。这个例子里还有一个小陷阱单独一个元素4是正数但它只代表‘从当前位置开始的一段’不是全局最优。真正最优的区间往往需要容忍中间出现负数因为负数的后面可能跟着更大的正数。如果你一看到负数就停下来那很容易漏掉正确答案。这个问题之所以经典不只是因为它常出现在各类算法考核里更因为它背后藏着动态规划、贪心思想、分治策略三条完全不同的求解路径。把它的解法吃透你再去写其他“区间最值类”问题思路会顺很多。1.2 暴力解法为什么很快会遇到瓶颈拿到这个问题第一直觉通常是枚举所有可能的起点和终点然后把区间里的每个数加起来找到最大值。逻辑上完全没有毛病但代价非常可观。暴力枚举分三层循环外层枚举起点i中层枚举终点j内层从i加到j。假如数组长度是n区间数量有n*(n1)/2个每个区间平均长度也是O(n)所以总时间复杂度是O(n^3)。当n 1000时粗略估计要执行上亿次加法能明显感觉到卡顿当n 10000时n^3就是一万亿次运算直接不可用。很多人会想那不是可以先算出前缀和用前缀和之差来求区间和吗没错加了这层优化之后只需要两层循环复杂度降到了O(n^2)但依然不是我们希望的结果。如果数组有十万个元素n^2就是一百亿次操作在线性时间就能解出的问题没必要付出这么大的代价。从算法设计角度看暴力解法之所以“笨”是因为它做了大量重复计算。同一个区间换一个起点或终点就得重新累加一遍。真正聪明的解法要么利用已经算出的历史信息要么从问题的结构中找到能合并、能复用的部分。接下来我们要讲的动态规划就是冲着“复用历史信息”这一目标去的。2. 动态规划从朴素前缀和到Kadane算法的推演2.1 用前缀和把暴力枚举降到 O(n²)在正式引入动态规划之前先把前缀和这个工具说清楚。前缀和数组prefix[i]表示原数组从第 0 项到第 i 项的和。预处理前缀和只需要O(n)时间之后任意区间[l, r]的和都能通过prefix[r] - prefix[l-1]快速得到不用再逐个累加。基于前缀和的枚举思路是这样的先算好prefix然后枚举起点i再枚举终点j用prefix[j] - prefix[i-1]直接得到sum(i..j)更新答案。总共两层循环复杂度O(n^2)。空间上多了一个前缀和数组也是O(n)。我提它不是为了让你去写这个版本而是要强调一个思维转变我们要的不是“如何更快地计算每个区间的和”而是“能不能在遍历一遍的过程中直接记住最有用的信息”。前缀和把区间和变成了两个独立量的差这个思想在后面长度受限的子序列问题里还会用到。先把这个概念刻在脑子里。O(n²) 的版本虽然不理想但它是理解最优解的一个跳板。你可以在本地跑一下观察当n从一千涨到一万时耗时如何指数上升这会让你更直观地理解后面线性算法带来的巨大收益。2.2 换一种状态定义递推公式自然出现动态规划的关键是状态定义。很多初学者之所以觉得 DP 抽象是因为状态定义没有找对。对于最大连续子序列和核心思路是不看“全局最优”而是看“以每个位置结尾的最优连续子段”。我定义dp[i]为“以原数组第i个元素作为结尾的连续子数组的最大和”。请注意“作为结尾”这四个字这是决定递推能否成立的关键。考虑第i个元素nums[i]以它结尾的连续子数组只有两种情况要么它自己单独成为一个子数组要么它接在以i-1结尾的某个最大连续子数组后面。于是递推公式就出来了dp[i] max(nums[i], dp[i-1] nums[i])为什么要比较这两个值因为如果dp[i-1] nums[i] nums[i]说明把nums[i]接到前面的区间后面能获得更大和那前面的累加值是有正贡献的如果反过来说明前面的累加值已经减分到了负数那不如干脆不要从nums[i]重新开始一个新的区间。这个“还剩下正收益就继续带变负了果断抛弃”的思路就是整个算法最核心的直觉。拿前面那个数组来走一遍过程nums[0] -2dp[0] -2nums[1] 1比较max(1, -21) 1dp[1] 1nums[2] -3比较max(-3, 1-3) -2dp[2] -2nums[3] 4比较max(4, -24) 4dp[3] 4nums[4] -1比较max(-1, 4-1) 3dp[4] 3nums[5] 2比较max(2, 32) 5dp[5] 5nums[6] 1比较max(1, 51) 6dp[6] 6nums[7] -5比较max(-5, 6-5) 1dp[7] 1nums[8] 4比较max(4, 14) 5dp[8] 5dp数组最大值是 6所以全局答案就是 6。这里有一个经常被忽略的点全局答案不是dp[n-1]而是所有dp[i]里取最大值。最后一个dp只表示“以最后一个数结尾的连续子数组”的最大和它并不能代表整个数组的全局最优。很多人在这一步翻车以为算完最后一个状态就结束了。索引 i012345678nums[i]-21-34-121-54dp[i]-21-2435615从这张表能清楚看到dp[6] 6是全局最大值而不是最后一个dp[8] 5。2.3 滚动变量Kadane算法的最终形态有了递推公式其实已经可以写出O(n)时间、O(n)空间的动态规划版本了。再进一步观察递推公式中dp[i]只依赖dp[i-1]这说明我们根本不需要保留整个dp数组只需要一个变量记录“以当前位置结尾的最大连续子数组和”再拿一个变量记录“到目前位置为止见过的最优答案”就够了。这就是著名的 Kadane 算法。它的核心代码极短但信息密度很高def max_sub_array(nums): if not nums: return 0 max_ending_here nums[0] max_so_far nums[0] for x in nums[1:]: max_ending_here max(x, max_ending_here x) max_so_far max(max_so_far, max_ending_here) return max_so_far用 C 写也一样int maxSubArray(vectorint nums) { if (nums.empty()) return 0; int maxEndingHere nums[0]; int maxSoFar nums[0]; for (int i 1; i nums.size(); i) { maxEndingHere max(nums[i], maxEndingHere nums[i]); maxSoFar max(maxSoFar, maxEndingHere); } return maxSoFar; }为什么能滚动因为我们在从左往右扫描时只需要知道上一个位置结尾时的最优和。这个局部状态一旦被当前元素更新完旧值就再也没有其他用处了。所以两个变量足够max_ending_here是“当前状态”max_so_far是“全局历史最优”。整个算法的时间复杂度是O(n)空间复杂度是O(1)。还有一点值得说一下有人把 Kadane 算法归类为“贪心”因为它确实在局部做“要不要继续带上前面”的决策但更多教材把它归类为“动态规划的滚动数组优化”因为它本质上是状态转移只是把状态数组压成了两个变量。叫什么不重要关键是你要能用自己的话解释清楚每一步在干什么。3. 再往深走分治、线段树和经典变体3.1 分治设计跨中点的最大值如何计算动态规划能够在线性时间解决这个问题但从“算法设计方法论”的角度分治解法依然值得掌握。它把数组从中间劈成两半那么全局最大连续子序列只有三种情况完全在左半部分、完全在右半部分、或者横跨中点。左半和右半的情况可以递归求解真正的难点是怎么计算跨越中点的最大和。横跨中点的区间一定由“中点向左延伸的连续一段”和“中点右侧延伸的连续一段”拼起来。于是我们从中点出发向左累加记录过程中能得到的最大和再从中点右侧第一个位置出发向右累加记录过程中能得到的最大和。这两个最大和相加就是跨越中点的最大连续子序列和。分治的复杂度是O(n log n)因为每一层的合并需要线性扫描一遍递归层数是log n。它虽然不如 Kadane 的O(n)但体现了一种通用的处理区间问题的思想分而治之再处理跨界的部分。很多其他算法比如归并排序的“跨分界点统计”用的也是同一个套路。这里贴一个相对规整的分治实现import math def cross_max(nums, l, mid, r): left_sum -math.inf cur 0 for i in range(mid, l - 1, -1): cur nums[i] left_sum max(left_sum, cur) right_sum -math.inf cur 0 for i in range(mid 1, r 1): cur nums[i] right_sum max(right_sum, cur) return left_sum right_sum def max_sub_array_rec(nums, l, r): if l r: return nums[l] mid (l r) // 2 left_ans max_sub_array_rec(nums, l, mid) right_ans max_sub_array_rec(nums, mid 1, r) cross_ans cross_max(nums, l, mid, r) return max(left_ans, right_ans, cross_ans)注意跨界计算时左右两部分都必须是从中点或中点右侧出发连续延伸的不能跳过任何一个负值。这里的“最大后缀”和“最大前缀”各自独立但它们拼在一起一定是一段连续区间所以相加是合法的。3.2 线段树节点能同时维护四个量支持动态修改Kadane 算法处理的是静态数组一次查询给出答案。但如果数组中的元素会被反复修改然后你还要频繁查询任意区间的最大连续子序列和Kadane 就不够用了。这时候线段树是一种很自然的进阶方案。线段树的每个节点代表一段连续区间我维护四个信息sum区间内所有元素之和lmax包含区间左端点的最大连续子序列和rmax包含区间右端点的最大连续子序列和tmax整个区间内部的最大连续子序列和合并两个子区间时规则如下sum left.sum right.sum lmax max(left.lmax, left.sum right.lmax) rmax max(right.rmax, right.sum left.rmax) tmax max(left.tmax, right.tmax, left.rmax right.lmax)这四个量的合并非常优雅lmax要么完全来自左子区间的左侧要么是整个左子区间再加上右子区间从左端点开始的最大段rmax同理tmax要么完全在左要么完全在右要么横跨左右两个子区间的连接处。有了这套合并规则单点修改时的更新只需要从叶子一路合并到根复杂度O(log n)区间查询时把命中的若干节点按顺序合并成一个临时节点同样能得到该区间的四个量最终答案是tmax。线段树版本代码相对长一些但核心就是这个节点定义和merge逻辑。理解它不仅能解决这道题还能迁移到很多需要动态维护区间信息的场景中比如“动态最大前缀和”“动态最大后缀和”等。3.3 三个高频变体环形数组、最大子矩阵、长度受限掌握了基础形态你再遇到类似问题就会感到“这题我见过”。我个人在项目里和给朋友做辅导时遇到最多的三个变体这里一起列出来。第一个是环形数组。数组头尾相连允许跨越边界取连续段。做法是最大环形子数组和等于整个数组的总和减去最小连续子序列和因为跨越边界的最优段等价于从中间挖掉一段和最小的连续段。不过要特别小心“全部为负数”的情况这个时候挖掉最小负段反而让总和变大但应该直接返回常规 Kadane 的结果也就是最大负数。所以环形版本的答案通常是max(常规最大和, 总和 - 最小子段和)如果后者对应的区间是空集则忽略。第二个是二维矩阵最大子矩阵和。给你一个m x n的矩阵求某个子矩阵的最大元素和。朴素做法是枚举上边界和下边界然后把每一列的元素累加成一维数组对这个一维数组跑 Kadane。枚举上下边界是O(m^2)每个一维数组跑 Kadane 是O(n)总复杂度O(m^2 n)。这个技巧在实际场景中很有用比如分析一段时间内多指标叠加后的最优时间段。第三个是限制长度至少为 K 的连续子序列。用前缀和数组可以解决固定子数组右端点i我们要找左端点j i-K1使得prefix[i] - prefix[j-1]最大。也就是说在移动到当前位置之前维护前i-K个前缀和的最小值然后相减。如果还要求长度不超过某个上限那就需要用单调队列维护滑动窗口里的前缀和最小值这也是“滑动窗口 前缀和”这类题目的标准解法。这三个变体看起来千变万化但底层的核心都是连续区间的和等于前缀和之差而最大问题可以靠动态规划或单调结构来优化。把基础吃透变体就只是换了一层皮。4. 实战防坑手册边界条件、常见误区和工程落地4.1 最容易写错的边界条件先聊空数组。题目如果明确数组非空那可以直接取nums[0]作为初始值。但如果实际工程里可能拿到空数组一定要单独处理。Kadane 遇到空数组会直接越界崩溃这是我见过最多次的低级错误。再聊全负数数组。假如输入是[-3, -1, -8]最大连续子序列和应该是-1也就是最大的那个负数。很多人习惯把max_so_far初始化为 0结果全负数时返回 0但这显然是错的因为子数组至少包含一个元素。正确做法是初始化成nums[0]或者在循环里用-inf来兜底。还有一个容易被忽视的点是数值溢出。数组元素和区间长度可能很大例如一万个百万级别的数加起来就是百亿级别32 位整数根本放不下。C 里建议用long longJava 里用longPython 里则不需要担心。我在某个模拟后台数据统计项目里就遇到过这个问题由于没考虑用 64 位线上结果在特殊数据下直接溢出排查了很久才发现是类型太窄。边界场景常见错误正确做法空数组取nums[0]导致崩溃先判断长度并返回 0 或抛出异常全负数初始化 0返回 0初始化nums[0]或-inf元素累加溢出int 溢出变负数使用 64 位整数数组长度 1循环没跑直接返回唯一元素4.2 面试和笔试里反复出现的理解误区误区一以为一遇到负数就必须断开。这是一个很常见的直觉错误因为最大连续子序列并不要求每个元素都是正数。只要前面的累计和还是正的那它就能给后面的元素“托底”。比如[5, -1, 100]最优区间显然是整段[5, -1, 100]如果在-1处断开你就只拿到了[100]白白丢掉 4。只有当累计和变成负面影响时才值得从当前位置重新开始。误区二把dp[i]理解成“前 i 个元素的最大连续子序列和”。这样理解会导致递推写成dp[i] max(dp[i-1], dp[i-1] nums[i])听起来合理但实际上忽略了“连续”这个约束。因为你可能选了前面的某个最优区间它并不以i-1结尾那加上nums[i]之后新的序列就不连续了。所以状态定义必须强调“以第 i 个元素结尾”。误区三只求状态不求具体区间。很多工程问题不仅要最大和还要知道是哪一段。如果只记住最大和落库时根本定位不了问题区间。这时候需要在 Kadane 更新最优答案时一并记录起止索引不能只更新一个数字。误区四误以为 Kadane 能直接处理二维矩阵。二维矩阵必须要先压缩维不能直接把 Kadane 套到二维数组上除非你把每一行或每一列当作一个整体来累加。4.3 真实项目中的落地姿势与区间记录很多非算法岗的朋友会问这种经典算法在真实系统里真的有用吗我的回答是太常用了。我曾经参与过一个模拟系统性能监控项目每天要扫描几十万个连续的时间窗口找出累计延迟最高的一段。背景噪声很大单点偶发高延迟并不能说明问题真正要抓的是“持续一段时间整体偏高”的区间。这正是最大连续子序列和的用武之地先把每个时间点的指标值做差分或标准化然后对处理后的序列跑 Kadane定位到具体的开始时间和结束时间。定位区间的代码稍微改一下就好def max_sub_array_with_index(nums): max_ending_here nums[0] max_so_far nums[0] start end 0 temp_start 0 for i in range(1, len(nums)): if nums[i] max_ending_here nums[i]: max_ending_here nums[i] temp_start i else: max_ending_here max_ending_here nums[i] if max_ending_here max_so_far: max_so_far max_ending_here start temp_start end i return max_so_far, start, end这里的关键是temp_start只在“重新开始”的时候更新而start只在“刷新全局最优”的时候更新。如果你每轮都更新start记录到的起点就会错乱。这个细节我在实际写监控组件时踩过坑后来加了一个临时变量来保存“候选起点”才彻底解决。工程落地的时候还要注意一个点原始序列可能很长如果直接套 Kadane遇到单个极端值就可能让累计和瞬间放大。所以我会先做归一化或限制单点贡献否则算法找到的区间和业务想表达“持续偏高”的语义不完全一致。这是算法之外的经验但比算法本身更能决定项目成败。5. 写在最后的个人体会做算法训练也好做工程优化也好最大连续子序列和这道题都值得反复咀嚼。我第一次学的时候只记住了 Kadane 的三行代码结果面试官一问“为什么这样写”我瞬间卡壳。后来我把暴力、前缀和、动态规划、分治、线段树这几种解法全部手写了一遍才真正理解它为什么能在线性时间完成。我个人在实际项目里用过最多的是带索引记录的 Kadane 版本以及线段树版本。前者用来快速定位监控指标异常区间后者用来处理用户行为序列里频繁修改、频繁查询的动态场景。你会发现只要理解了“状态定义”和“区间合并”这两个看似复杂的工具都变得很自然。最后再分享一个小技巧如果你刚开始学千万别只背代码试着在纸上手推一遍递推表把dp[i]和max_so_far的关系画出来。这一步做完后面所有变体题你基本都能一眼看穿。算法这件事真正难的从来不是代码而是你愿不愿意把每个细节都抠清楚。