这个问题在算法圈子里几乎快被讲烂了但“烂大街”不代表人人都真懂。我刚带完一个内部算法小组发现很多工作了三五年的工程师让他手写一个最大连续子序列的DP状态转移方程能写对但一问到“为什么状态要这样定义”“如果数组全是负数怎么办”“能不能把具体子序列也输出出来”立刻就卡壳了。这恰恰说明大部分人对这个经典问题的理解还停留在“背答案”的层面。这篇我就把DP求解最大连续子序列和这件事从头到尾掰开揉碎讲一遍从暴力枚举到状态设计从一维代码到二维矩阵扩展该给的推导给推导该踩的坑也替你踩一遍直接可以拿去面试和实战用。1. 从一道“最简单”的难题说起问题定义与暴力起点最大连续子序列这个问题其实最早是从“最大子段和”这个经典题目来的后来因为LeetCode 53题而彻底火遍全网。题面很简单给你一个整数数组nums请你找出一个具有最大和的连续子数组子数组最少包含一个元素返回其最大和。比如[-2, 1, -3, 4, -1, 2, 1, -5, 4]答案是6因为[4, -1, 2, 1]的和最大。很多初学者看到“连续”两个字没什么感觉但恰恰是“连续”这个约束把问题的难度从“排序后取前k个”那种级别拉到了一个需要认真设计算法的级别。子数组必须保持原数组中的相对顺序不能跳跃取元素这就意味着简单的贪心排序思路直接失效。我在面试候选人的时候经常让他们先讲讲对这个问题的第一反应。十个人里有六七个会先说“那就暴力枚举嘛”。没错暴力确实能解这也是理解后续优化最自然的起点枚举所有的子数组起点i和终点j计算nums[i]到nums[j]的和然后取最大值。这个思路的时间复杂度是 O(n³)如果预先用前缀和处理区间和可以优化到 O(n²)但本质上还是双重循环枚举。具体来说前缀和的做法是这样的先预处理一个prefix数组prefix[i]表示nums[0]到nums[i-1]的和。这样任意区间[l, r]的和就可以用prefix[r1] - prefix[l]在 O(1) 时间内算出来。于是枚举起点和终点依次比较所有区间和的最大值总复杂度 O(n²)。但是当数据规模来到十万甚至百万级别时O(n²) 就是灾难。这也是为什么需要动态规划介入的根本动因——我们希望把“重复计算”和“无谓枚举”都消除掉让算法逼近 O(n)。注意这里有一个很容易被忽略的点子数组“至少包含一个元素”。这就意味着就算数组里全是负数也不能返回“空数组的和 0”而必须从负数里挑一个最大的。这个边界条件在后面推导状态转移方程时极其关键很多人在这里栽跟头。2. 为什么暴力枚举浪费得离谱从重复子问题看DP的动机要理解动态规划为什么是这个问题的最优解法光说“暴力太慢”是不够的得看清楚暴力枚举到底浪费在了哪里。这个“看清浪费”的过程就是动态规划思想的入口。考虑一个数组[a, b, c, d]暴力枚举时我们会分别计算[a]、[a,b]、[a,b,c]、[a,b,c,d]的和然后计算[b]、[b,c]、[b,c,d]的和再计算[c]、[c,d]的和。注意[b,c,d]这个区间我们明明已经在算[a,b,c,d]的时候把后面三个元素加过一遍了但暴力解法完全不会复用这个中间结果它只是机械地从头加到尾。这种“重复计算同一个后缀或子区间”的现象在动态规划里叫重叠子问题。最大连续子序列问题天然具备这个结构你在算某个位置结尾的最大和时其实依赖了前一个位置结尾的最大和这个子结果。如果把这个子结果缓存下来就能避免重复扫描。再往下想一层为什么这个问题具备“最优子结构”呢假设我们已经知道了“以第i个元素结尾的最大子数组和”dp[i]那么想求“以第i1个元素结尾的最大子数组和”dp[i1]只需要做一个决策是把nums[i1]接到前面那个子数组的后面还是让它自己单独成为一个新子数组。这个决策的本质是前面那个子数组对我有没有“正贡献”。如果dp[i]本身是负数那把它接在nums[i1]前面只会拖累后面的元素所以不如从nums[i1]重新开始。如果dp[i]是正数那接上去就是锦上添花让整体和更大。这种“要么延续前面的最优解要么从头开始”的两选一决策就是动态规划里最经典的“状态转移”模型。和背包问题、最长上升子序列一样核心都是把大问题拆成小问题用小问题的最优解递推大问题的最优解。所以暴力枚举的浪费在于没有利用问题的递推结构而动态规划的精髓恰恰是把这种递推结构显式地提炼出来用一张一维的表或者少数几个变量去存储中间状态。这也是我把这个题目当作“DP入门第一课”的原因——它足够简单但又完整地体现了动态规划的所有核心思想。3. 状态定义是DP的灵魂dp[i] 为什么非得表示“以第 i 个元素结尾”动态规划最关键也最容易卡住新手的一步不是写转移方程而是定义状态。同一个问题状态定义得好转移方程就是一行代码状态定义得别扭后面全是坑。最大连续子序列这个问题最常见的状态定义就是dp[i]表示以nums[i]作为结尾元素的最大连续子数组和。注意这里有个“必须包含nums[i]”的隐含约束。为什么要这样定义这是整道题的题眼值得展开讲清楚。我们的目标数组是“连续的一个子段”它必定有一个结尾位置。如果我们能把“以每个位置结尾的子段的最大和”都算出来那么整个数组的答案就是在所有这些“结尾位置”里取最大值。这样做的好处是每个状态的问题结构一致转移时只需要考虑当前元素和之前状态的关系不用关心前面的子段具体从哪里开始。假设状态定义换成“dp[i]表示nums[0..i]这个前缀中的最大子数组和”听起来好像也行但转移方程就没法写了。因为dp[i1]并不知道dp[i]对应的那个最优子数组到底以哪里结尾也就无法判断能不能和nums[i1]拼在一起。你可能会想同时记录下来但那样状态就膨胀了逻辑也复杂得多。所以“以nums[i]结尾”这个约束不是随便加的它保证了状态之间的承接关系是确定的dp[i]的后续只有唯一一种可能就是接上nums[i1]或者不接。这个“确定性的转移方向”是动态规划能高效工作的根基。再来推导转移方程。根据dp[i]的定义以nums[i]结尾的子数组只可能有两种情况第一种是只有nums[i]自己一个元素第二种是nums[i]加上“以nums[i-1]结尾的最大子数组”。哪种更好取两者中的较大值。dp[i] max(nums[i], dp[i-1] nums[i])这个式子还可以写成更常见的形式dp[i] max(dp[i-1], 0) nums[i]。两个写法等价不过第一种写法更直观地体现了“两选一决策”。边界条件是dp[0] nums[0]因为第一个元素只能自己作为子数组。最终的答案是max(dp[0], dp[1], ..., dp[n-1])而不是dp[n-1]——这个“不是最后一个状态”的点非常容易出错我在后面讲实现细节时还会再强调。4. 从纸上公式到跑通代码一维DP实现的五个细节理论推导完毕接下来是动手实现。很多教程给出一段代码就结束了但实际写代码时有几个细节会直接影响正确性和效率我一个个说清楚。4.1 最朴素的DP数组版实现先给出最容易理解的版本用一个dp数组把每个位置的状态都存下来。这样虽然多花了 O(n) 的空间但过程完全透明方便对照上面推导的公式。def maxSubArray(nums): n len(nums) dp [0] * n dp[0] nums[0] for i in range(1, n): dp[i] max(nums[i], dp[i-1] nums[i]) return max(dp)两点需要说明。第一循环从1开始因为dp[0]已经初始化好了。第二为什么返回值是max(dp)而不是dp[-1]因为dp[i]只表示“以nums[i]结尾”的最大和但全局最大和的子数组可能以任意位置结尾。比如数组[1, -2, 3]dp [1, -1, 3]全局答案是3对应dp[2]但假如数组是[2, -1, 1]dp [2, 1, 2]全局答案是2对应dp[0]。不取max就会得到错误结果。4.2 空间优化只需要两个变量观察转移方程dp[i]只依赖dp[i-1]不需要更早的状态。因此完全可以用一个变量滚动更新把空间复杂度压缩到 O(1)。这也是面试官最常要求的优化。def maxSubArray(nums): cur nums[0] # 以当前位置结尾的最大和 best nums[0] # 全局最大和 for i in range(1, len(nums)): cur max(nums[i], cur nums[i]) best max(best, cur) return best这里的cur对应dp[i]best对应历史所有dp值的最大值。每次循环先更新cur再更新best顺序不能反。我见过有人把best max(best, cur)写在cur更新之前结果答案少算了当前这一次的状态排查半天才找到问题。4.3 全负数数组的边界情况这一点单独拎出来讲因为实在太容易踩坑了。如果数组是[-3, -5, -2]上面代码的运行过程是cur初始为-3best初始为-3i1时cur max(-5, -3 (-5)) -5best保持-3i2时cur max(-2, -5 (-2)) -2best max(-3, -2) -2。最终结果是-2即最大的那个负数。这个行为符合题意子数组不能为空。但有些变体题比如“最大子序列和允许选空子数组”答案就变成了0那种题需要在初始化时把best设为0且遇到正数才更新。我在力扣上看到不少人在讨论区争论这个问题其实不是代码问题而是题目条件定义不同。4.4 如果还要输出具体子数组记录起点和终点很多时候面试官会追加一问“光给最大和不够把那个子数组也给我输出出来。”这需要我们在更新cur时同步记录起点。def maxSubArray_with_indices(nums): cur nums[0] best nums[0] start 0 best_start 0 best_end 0 for i in range(1, len(nums)): if cur nums[i] nums[i]: # 延续之前的子数组 cur cur nums[i] else: # 从当前元素重新开始 cur nums[i] start i if cur best: best cur best_start start best_end i return best, nums[best_start:best_end1]核心技巧是当决策为“延续”时起点start保持不变当决策为“重新开始”时起点更新为当前下标i。这里有一个判断细节我用的是cur nums[i] nums[i]当两者相等时选择延续这样能保证在有多个等和子数组时输出的是最靠前的那个。如果你更想要靠后的改成就行。4.5 复杂度分析为什么说这是最优解这个算法的时间复杂度是 O(n)只需要遍历一次数组空间复杂度是 O(1)。在比较排序、哈希等手段都无法改变“必须至少看一眼每个元素”的前提下O(n) 已经是理论最优了。这也是它能成为面试经典题的原因——解法简单优雅但要证明它最优、要处理各种边界都需要真功夫。5. 从一维到进阶四个高频变体与扩展解法光是会做裸题还不够面试官最爱干的事就是“加条件”。这里整理四个我实际遇到过的扩展版本每一个都在一维DP基础上做了有针对性的改造。5.1 变体一环形数组上的最大连续子序列题目改成数组首尾相接成一个环求最大连续子序列和。比如[5, -3, 5]普通数组最大和是7[5, -3, 5]但环状数组还可以取[5, 5]掐头去尾跨过首尾连接处答案是10。解法思路很经典环形数组的最大子序列和要么来自普通数组的“非跨越首尾”的子数组要么来自“跨越首尾”的子数组。第二种情况等价于整个数组的总和减去“最小连续子序列和”。因为跨越首尾的最大段剩下的部分就是数组中间一段最小的连续段。所以代码实现分为两步用一维DP求出最大子序列和max_sum再求最小子序列和min_sum答案就是max(max_sum, total_sum - min_sum)。这里有个坑如果数组全是负数total_sum - min_sum会计算出 0因为min_sum total_sum但子数组不能为空所以这种情况要特殊处理直接返回max_sum。def maxSubarraySumCircular(nums): total sum(nums) cur_max nums[0] best_max nums[0] cur_min nums[0] best_min nums[0] for i in range(1, len(nums)): cur_max max(nums[i], cur_max nums[i]) best_max max(best_max, cur_max) cur_min min(nums[i], cur_min nums[i]) best_min min(best_min, cur_min) if best_max 0: return best_max return max(best_max, total - best_min)这个解法本质上是把“环状”转化为“两次一维DP”思维量不大但那个全负数的特判很容易漏漏了就会得到错误的0。5.2 变体二返回具体的最大和子序列本身这个我在上面已经给了带起点终点记录的代码但面试中还有另一种问法“子序列不要求连续任意选取若干元素保持相对顺序求最大和。”注意这是另一个问题了叫“最大子序列和”不是“最大连续子序列”。区别在于能不能断开。如果允许断开那就是个简单得多的题把所有正数加起来就行因为不要求连续所有正数都可以选负数全部跳过。但如果同时要求“至少选一个”那遇到全负数数组时答案就是最大的那个负数。这个变体经常被拿来和原题对比考察候选人是否真正理解了“连续”二字的含义。5.3 变体三二维矩阵中的最大子矩阵和把问题从一维数组升级到二维矩阵求一个子矩阵使它的元素和最大。比如一个m x n的矩阵要求输出最大子矩阵的和。这个问题可以直接用一维DP作为子过程来解。核心思路是枚举矩阵的上下边界。固定上下边界top和bottom后把每一列在这两条边界之间的元素纵向求和得到一个长度为n的一维数组col_sum。此时“最大子矩阵和”就等价于“这个col_sum数组的最大连续子序列和”。用一维DP解决后再枚举所有可能的上下边界取最大值。def maxSubMatrix(matrix): if not matrix or not matrix[0]: return 0 rows, cols len(matrix), len(matrix[0]) ans matrix[0][0] 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] cur col_sum[0] best col_sum[0] for c in range(1, cols): cur max(col_sum[c], cur col_sum[c]) best max(best, cur) ans max(ans, best) return ans复杂度为 O(m²n)其中m是行数n是列数。这个技巧在面试里非常加分因为它展示了你“把高维问题降维”的能力。实际工程中图像处理里的最大亮斑检测、金融里的最大收益时间段分析也都能归约到类似模型。5.4 变体四乘积最大的连续子序列LeetCode 152题求乘积最大的连续子数组。这个变体坑就坑在“负负得正”所以只维护最大值不够了还必须同步维护最小值。def maxProduct(nums): cur_max nums[0] cur_min nums[0] ans nums[0] for i in range(1, len(nums)): x nums[i] candidates (x, cur_max * x, cur_min * x) cur_max max(candidates) cur_min min(candidates) ans max(ans, cur_max) return ans这个版本我已经在项目里实际跑过对[-2, 3, -4]这样的用例也能正确输出24[ -2, 3, -4]乘积为 24而如果只维护最大值会在[-1, -2, -9, -6]上翻车。它和一维最大和DP的差别在于状态从一个变成了两个最大和最小转移也变成了三者取最值。理解了“连续子序列DP”的框架这个变体其实就是加了一个维度的状态。6. 实战对比分治法和DP怎么选以及DP思路在工程里的延伸其实最大连续子序列求和还有一个经典的 O(n log n) 解法分治法。把数组从中间分开最大子数组要么完全在左半要么完全在右半要么跨越中点。跨越中点的情形需要从中间分别向左右扩展计算最大后缀和与最大前缀和。我在实际编码中发现分治法虽然复杂度不如DP但它提供了另一种思考角度而且在一些“必须返回子树/区间信息”的问题上更好用。比如第4.4节要求“同时输出子序列本身”时分治也能做到但代码比DP长得多。所以我个人对这个问题的选型原则很明确追求最优时间复杂度和代码简洁用DP如果需要维护额外信息、需要递归结构去处理子问题才考虑分治。解法时间复杂度空间复杂度优点缺点暴力枚举O(n³)O(1)思路直接超大数据完全不可用前缀和 枚举O(n²)O(n)能输出所有区间和仍然太慢分治法O(n log n)O(log n)思路优雅适合递归场景代码量大常数大动态规划O(n)O(1)最优复杂度实现简单必须理解状态定义才能扩展很多人在工程中一碰到“连续区间的某种极值问题”第一反应是滑窗或者线段树。滑窗适合“窗口大小固定或单调移动”的问题线段树适合“区间查询 区间更新”的在线场景。而“最大连续子序列”这类问题它的子数组长度不固定也没有单调性滑窗解决不了如果查询是静态的DP一遍过是最快的如果数组会动态更新那确实要上线段树维护前缀最小和。这个选型判断在真实业务里很重要不是所有“区间和最大”都能无脑套DP。另外这个DP思想在工程中还可以抽象成一个更通用的模式在线上数据流处理中如果我们要持续维护“到目前为止的最优连续段”就可以用滚动变量cur和best不断更新而不需要保存整个历史数组。这在流式计算、实时监控指标分析中非常实用。7. 面试被问到这个题三个追问和一个必背模板最后说说面试场景。最大连续子序列是高频题而且面试官几乎必然会追问扩展。根据我之前刷题和面试别人的经验有四个点是被问得最频繁的。7.1 追问一你能把空间优化到O(1)吗这个问题上面已经回答过了直接用cur和best两个变量滚动更新即可。注意要强调dp[i]只依赖dp[i-1]这是能滚动更新的前提。7.2 追问二如果数组里有正有负还能用贪心吗严格来说这个问题本身就可以用贪心思路解释从左往右遍历只要当前累计和是正数就继续累加一旦累计和为负就丢弃并从下一个元素重新开始。这个贪心策略和DP结果一致但它其实是DP的一种直观解释。面试时我建议先讲DP再讲贪心等价性能体现你对问题本质的理解。7.3 追问三状态转移方程还能怎么变形dp[i] max(nums[i], dp[i-1] nums[i])可以写成dp[i] max(dp[i-1], 0) nums[i]两者完全等价。后面的写法在说明“负前缀直接丢弃”时很有说服力。另一个变形是维护“前缀和最小值”的思路最大子数组和 当前前缀和 - 之前出现过的最小前缀和。def maxSubArray_via_prefix(nums): min_prefix 0 cur_prefix 0 best nums[0] for x in nums: cur_prefix x best max(best, cur_prefix - min_prefix) min_prefix min(min_prefix, cur_prefix) return best这个写法在处理“数组动态添加元素随时查询最大连续子段和”时特别好用配合线段树就是动态区间最大子段和的解法。7.4 一个可以直接背的通用模板如果面试时间紧你只需要记住这份Python模板def maxSubArray(nums): cur best nums[0] for x in nums[1:]: cur max(x, cur x) best max(best, cur) return best这个模板的通用性很强把max换成min就是最小连续子序列把x换成x, cur*x的二元组就是最大连续子序列乘积问题把一维数组换成二维矩阵列压缩就是最大子矩阵问题。背模板没问题但一定要理解每一行的含义尤其是cur max(x, cur x)这个决策到底在做什么。我在这几年的面试和带人经历里见过太多候选人把模板背得滚瓜烂熟结果一追问“为什么cur x要跟x取 max”就解释不清。动态规划题目的价值从来不在于代码本身而在于从问题到状态定义、从状态定义到转移方程的思考路径。把这条路径理清楚了以后遇到任何变体你都不会慌。