这个问题在算法圈子里几乎快被讲烂了，但“烂大街”不代表人人都真懂。我刚带完一个内部算法小组，发现很多工作了三五年的工程师，让他手写一个最大连续子序列的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[r+1] - 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]，那么想求“以第i+1个元素结尾的最大子数组和”dp[i+1]，只需要做一个决策：是把nums[i+1]接到前面那个子数组的后面，还是让它自己单独成为一个新子数组。
这个决策的本质是：前面那个子数组对我有没有“正贡献”。如果dp[i]本身是负数，那把它接在nums[i+1]前面只会拖累后面的元素，所以不如从nums[i+1]重新开始。如果dp[i]是正数，那接上去就是锦上添花，让整体和更大。
这种“要么延续前面的最优解，要么从头开始”的两选一决策，就是动态规划里最经典的“状态转移”模型。和背包问题、最长上升子序列一样，核心都是把大问题拆成小问题，用小问题的最优解递推大问题的最优解。
所以，暴力枚举的浪费在于没有利用问题的递推结构；而动态规划的精髓，恰恰是把这种递推结构显式地提炼出来，用一张一维的表或者少数几个变量去存储中间状态。这也是我把这个题目当作“DP入门第一课”的原因——它足够简单，但又完整地体现了动态规划的所有核心思想。
3. 状态定义是DP的灵魂：dp[i] 为什么非得表示“以第 i 个元素结尾”
动态规划最关键也最容易卡住新手的一步，不是写转移方程，而是定义状态。同一个问题，状态定义得好，转移方程就是一行代码；状态定义得别扭，后面全是坑。
最大连续子序列这个问题，最常见的状态定义就是：dp[i]表示以nums[i]作为结尾元素的最大连续子数组和。注意，这里有个“必须包含nums[i]”的隐含约束。为什么要这样定义？这是整道题的题眼，值得展开讲清楚。
我们的目标数组是“连续的一个子段”，它必定有一个结尾位置。如果我们能把“以每个位置结尾的子段的最大和”都算出来，那么整个数组的答案，就是在所有这些“结尾位置”里取最大值。这样做的好处是：每个状态的问题结构一致，转移时只需要考虑当前元素和之前状态的关系，不用关心前面的子段具体从哪里开始。
假设状态定义换成“dp[i]表示nums[0..i]这个前缀中的最大子数组和”，听起来好像也行，但转移方程就没法写了。因为dp[i+1]并不知道dp[i]对应的那个最优子数组到底以哪里结尾，也就无法判断能不能和nums[i+1]拼在一起。你可能会想同时记录下来，但那样状态就膨胀了，逻辑也复杂得多。
所以，“以nums[i]结尾”这个约束不是随便加的，它保证了状态之间的承接关系是确定的：dp[i]的后续只有唯一一种可能，就是接上nums[i+1]或者不接。这个“确定性的转移方向”是动态规划能高效工作的根基。
再来推导转移方程。根据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初始为-3，best初始为-3；i=1时cur = max(-5, -3 + (-5)) = -5，best保持-3；i=2时cur = max(-2, -5 + (-2)) = -2，best = 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_end+1]核心技巧是：当决策为“延续”时，起点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”就解释不清。动态规划题目的价值从来不在于代码本身，而在于从问题到状态定义、从状态定义到转移方程的思考路径。把这条路径理清楚了，以后遇到任何变体，你都不会慌。
