前缀和与动态规划：最大子数组和的两种解法竟是同一个模型

刷 LeetCode 经典的动态规划题时53. 最大子数组和往往是最先遇到的几个题目之一。大多数解法会告诉你两种主流思路一种是 Kadane 算法动态规划另一种是用前缀和扫一遍。很多人习惯性地把这两者当成两个独立知识点去背一个叫线性 DP一个叫前缀和技巧。但我在反复推导后发现一个很有意思的事实——它们在数学结构上是同一个解法只是换了观察角度。这篇文章不会只停留在把代码贴出来、AC 就完事的层面而是想借这道题把前缀和与动态规划之间那条隐秘的等号彻底拆开看看两者到底是怎么互推的。无论你是在准备面试、打算法竞赛还是单纯想把基础吃透这条推导链路都会有用。1. 先看清问题在问什么三种视角下的同一道题1.1 题目本身怎么描述53. 最大子数组和的题干很简洁给定一个整数数组nums请你找出一个具有最大和的连续子数组子数组最少包含一个元素返回其最大和。一个经典例子是nums [-2,1,-3,4,-1,2,1,-5,4]答案是6对应的子数组是[4,-1,2,1]。另一个容易让人困惑的例子是全负数数组比如[-1,-2,-3]答案是-1因为子数组至少包含一个元素你被迫选一个最不烂的负数。1.2 暴力解先打底为什么它是 O(n^2)第一次遇到这道题绝大多数人的直觉是枚举所有子数组。固定左端点i然后枚举右端点j把nums[i..j]累加一遍。这样做的复杂度是 O(n^2)如果每段都重新求和就是 O(n^3)用前缀和优化到 O(n^2)。这种暴力做法不是没有意义它给了我们一个很朴素的区间结构认知最大子数组和 max_{0 i j n} sum(nums[i..j])把所有区间和都列出来取最大。这个式子本身是绝对正确的只是复杂度让人难受。能不能在保持找区间最大值这一语义不变的前提下把复杂度降下来这就引出了两个看起来不同、归宿相同的优化方向。1.3 两个优化方向的起点完全不同前缀和视角把sum(nums[i..j])表示成S[j] - S[i-1]问题变成在一堆前缀和中找两个位置让后一个减前一个最大。这个视角关心的是区间端点。动态规划视角不从区间端点下手而是定义f[i]表示以nums[i]结尾的最大子数组和然后思考f[i]怎么由f[i-1]转移来。这个视角关心的是结尾位置的状态。如果你只看代码前缀和解法长这样# 前缀和版本 def maxSubArray(nums): ans nums[0] prefix 0 min_prefix 0 # 注意初始值 for x in nums: prefix x ans max(ans, prefix - min_prefix) min_prefix min(min_prefix, prefix) return ans动态规划Kadane版本长这样# 动态规划 / Kadane 版本 def maxSubArray(nums): dp nums[0] ans nums[0] for i in range(1, len(nums)): dp max(nums[i], dp nums[i]) ans max(ans, dp) return ans两段代码的循环结构完全不同一个在维护历史最小前缀和一个在维护以当前元素结尾的最优段和。如果不去推导很难相信它们底层相通。这篇文章的核心任务就是把这两段代码中间的那层纸捅破。2. 前缀和视角推导维护历史最低点就是最优策略2.1 把区间和改写为前缀和之差设前缀和数组为S其中S[0] 0S[k] nums[0] nums[1] ... nums[k-1]这里用S[k]表示前 k 个元素之和可以让下标计算更清爽。那么任意连续子数组nums[i..j]的和可以写成sum(nums[i..j]) S[j1] - S[i]其中0 i j n。于是题目等价于求max_{0 i j n} (S[j] - S[i])注意这里j的取值范围是1..ni的范围是0..n-1而且要保证i j。换句话说我们要在S这个数组里找两个点一个点当被减数右下标一个点当减数左下标让差最大。这就是最大子数组和 前缀和数组中的最大落差。2.2 为什么维护一个历史最小前缀和就够了现在的问题是如何高效求出两个点的最大差而且要求右边的点必须在左边的点之后有一个很常用的在线算法思路我们遍历S数组的每个位置j把它当作被减数端点。此时为了让S[j] - S[i]最大S[i]应该尽可能小且i j。所以只要在遍历过程中不断记录已经出现过的前缀和最小值min_so_far那么以当前位置作为右端点时的最优答案就是S[j] - min_so_far。把这个操作翻译成人话你每走到一个位置就看看从历史某个最低点到现在能赚多少差价。这个差价的最大值就是最大子数组和。这里有个关键细节min_so_far的初始值必须是0而不是正无穷。原因很简单S[0] 0代表空数组的前缀和。子数组允许从nums[0]开始也就是说减数端点可以取到S[0]。如果初始化成float(inf)第一轮prefix - min_so_far会变成负无穷答案直接算错。2.3 复杂度与正确性的直观理解这个算法只有一次遍历时间复杂度 O(n)空间复杂度 O(1)不需要真的把S数组存下来只需要一个滚动变量prefix和历史最小值。为什么一个简单的min维护就能覆盖所有情况因为任何最优区间[i, j]的起点i对应的前缀和S[i]要么本身就是历史最小值要么在S[i]前面存在一个更小的前缀和。如果存在更小的前缀和那说明这个区间还能往左延伸得到更大的和——这与最优矛盾。更准确地说对于任意固定的右端点历史最小前缀和产生的区间一定不差于其他起点产生的区间。这个思想就是贪心正确性的核心。用一个例子跑一遍nums [-2, 1, -3, 4, -1, 2, 1, -5, 4] 前缀和 S: [0, -2, -1, -4, 0, -1, 1, 2, -3, 1]遍历 S 时走到-2历史最小0差值-2更新历史最小为-2走到-1差值-1 - (-2) 1走到-4更新历史最小为-4走到0差值0 - (-4) 4走到-1差值-1 - (-4) 3走到1差值1 - (-4) 5走到2差值2 - (-4) 6← 最大走到-3差值1走到1差值5最大差值6答案正确。对应的区间就是从S中-4的下一个位置到S中2的位置正好是[4,-1,2,1]。2.4 全负数数组的边界验证再跑一个边界用例nums [-1, -2, -3]。前缀和S [0, -1, -3, -6]。遍历过程如下走到-1差值-1 - 0 -1ans -1更新历史最小为 -1走到-3差值-3 - (-1) -2ans 仍为 -1更新历史最小为 -3走到-6差值-6 - (-3) -3ans 仍为 -1答案是-1正确。注意如果初始化min_so_far时用的是0而不是S[0]全负数情况下依然能保证第一个元素被纳入候选。3. 动态规划视角推导达到f[i]的选择只有两条路3.1 状态定义以nums[i]结尾而不是前 i 个元素动态规划的第一步是定义状态。这里最容易踩的坑是把状态定义成前 i 个元素中的最大子数组和然后试图从前 i-1 个元素的最优值直接转移。这个定义很难直接写出递推因为你不知道前 i-1 个元素的最优子数组结尾在哪里无法判断能不能接上nums[i]。正确的状态定义是设f[i]表示以nums[i]作为结尾元素的最大子数组和。也就是说子数组必须是形如nums[k..i]的一段且必须以i结尾。这个定义的好处是转移关系非常清楚。考虑f[i]对应的子数组它只有两种可能单独由nums[i]构成即k i和为nums[i]。接在f[i-1]对应的最优子数组后面即nums[k..i-1]接上nums[i]和为f[i-1] nums[i]。于是转移方程f[i] max(nums[i], f[i-1] nums[i])写成更常见的形式就是f[i] max(f[i-1], 0) nums[i]这两种写法完全等价因为当f[i-1] 0时max(nums[i], f[i-1] nums[i])等于nums[i]而当f[i-1] 0时答案一定是f[i-1] nums[i]更大。换句话说前缀状态如果是负数就果断丢弃从当前元素重新开始。3.2 为什么最终答案是所有f[i]的最大值这是初学者最常问的问题之一既然f[i]都是以 i 结尾的最大值那整体最大值是不是就应该出现在最后一个位置直接输出f[n-1]就行答案是否定的。f[i]的语义决定了它必须包含nums[i]所以f[i]只能描述结尾固定的子数组。而全局最优子数组的结尾位置我们是不知道的它在数组的任何位置都有可能。所以在计算完所有f[i]后还需要取一次最大值ans max(f[0], f[1], ..., f[n-1])举个例子nums [5, -10, 100]。f [5, -5, 100]最后一个f[2] 100恰好是答案。但如果换一组数据nums [5, -10, 6]f [5, -5, 6]最后一个f[2] 6而全局答案是f[0] 5吗也不是是6大于5所以还是最后一个。再换nums [5, -10, 4]f [5, -5, 4]答案其实是5它出现在f[0]而不是f[2] 4。这说明全局最优并不一定在数组末尾出现最后再扫一遍取 max或者在滚动过程中同步取 max是必须的。3.3 空间优化与滚动变量的由来从转移方程看f[i]只依赖f[i-1]不需要保留整个f数组。于是可以用一个变量dp表示以当前位置结尾的最大子数组和循环更新即可。这就是为什么常见题解里 Kadane 算法看起来只有两个变量dp nums[0] ans nums[0] for i in 1..n-1: dp max(nums[i], dp nums[i]) ans max(ans, dp)这里dp就是滚动后的f[i]ans负责记录历史最大值。空间复杂度降到 O(1)。3.4 动态规划解法的贪心味道仔细看转移方程f[i] max(f[i-1], 0) nums[i]你会发现它内部藏着一个贪心决策当f[i-1] 0时接着上一段总是优于从当前元素重新开始因为nums[i]加一个非负数不会更差。当f[i-1] 0时从当前元素重新开始必然优于接着上一段因为负数的前缀只会拖累当前元素。很多教材会把这个过程描述成局部最优达到全局最优的贪心但严格来说它依然是一个典型 DP——因为有明确的状态定义和转移方程。只是这个 DP 恰好有一个非常直观的贪心解释。后面的章节会进一步揭示Kadane 算法和前缀和版本在丢弃负数前缀这一点上表现出了完全一致的行为。4. 两份代码同一套决策严格互推与中间值对照4.1 用数学公式建立两个解法的映射关系这一节回答标题里提出的核心问题前缀和和动态规划怎么就是同一个解法了回顾前缀和版本的每一步prefix S[j] # 当前前缀和 ans max(ans, prefix - min_so_far) # 用当前点当右端点 min_so_far min(min_so_far, prefix)再看 Kadane 版本的每一步dp max(nums[i], dp nums[i]) ans max(ans, dp)为了把两者联系起来我们把dp用前缀和表示。dp是以nums[i]结尾的最大子数组和也就是说它在所有可能的起点k中选择是的最大值dp_i max_{0 k i} (S[i1] - S[k]) S[i1] - min_{0 k i} S[k]看到没有“以 i 结尾的最大子数组和” 恰好等于当前前缀和减去历史最小前缀和。这个公式把 DP 状态直接翻译成了前缀和语言。于是 Kadane 算法里的dp更新就等价于前缀和版本里的prefix - min_so_farKadane 算法里的ans取最大值等价于前缀和版本里对每个位置都算一次prefix - min_so_far再取最大值。两个循环在每一个时间步计算的是同一个数值。反方向的翻译也成立前缀和版本里维护min_so_far本质上就是在维护 DP 需要的最优起点。每走一步min_so_far都可能被更新为一个更小的前缀和这对应着 DP 里发现f[i-1]是负数果断丢掉前缀、从当前位置重新开始的决策。所以前缀和版本的min_so_far更新 → DP 的f[i-1] 0时重新开始前缀和版本的prefix - min_so_far→ DP 的f[i]前缀和版本的ans→ DP 的全局ans两个算法根本就是同一棵决策树只是前缀和版本把状态藏在了两个前缀和的差里。4.2 同一组数据两个算法的中间值逐轮对照光说公式可能不够直观我们拿nums [-2, 1, -3, 4, -1, 2, 1, -5, 4]走一遍把每一步的dp和prefix - min_so_far放在表格里对照轮次nums[i]前缀和 prefixmin_so_farprefix - min_so_fardp (Kadane)说明0-2-20-2-2都是从第一个位置开始11-1-211历史最低点 -2差值 1dp 选择从 1 重新开始2-3-4-2-2-2前缀和刷新历史最低差值回落340-444min 还没更新到 0因为 0 不比 -4 小dp 从 4 重新开始4-1-1-433521-455612-466最大值在这一轮出现7-5-3-411全局答案已锁定为 6841-455观察这张表每一轮的dp和prefix - min_so_far完全相等。这不是巧合而是由dp_i S[i1] - min(S[0..i])这个恒等式保证的。4.3 两种视角在实际编码中的差异虽然数学上等价但编码体验上还是有一些区别值得单独说边界条件的敏感度不同。前缀和版本对min_so_far的初始化极其敏感。如果你把min_so_far初始化为S[0]即nums[0]在有些写法里会出错因为它漏掉了空区间前缀和 0这个合法起点。而 Kadane 版本对初始化的理解更直接dp nums[0]不会有人搞错。对空子数组的默认态度不同。前缀和版本天然把S[0] 0当作一个候选起点这其实是允许了空子数组参与比较。如果题目要求子数组必须非空且数组全为负数你必须保证ans至少会被赋值一次例如把ans初始化为nums[0]或者用-inf然后用第一个元素兜底。Kadane 版本因为dp nums[0]起步天然满足非空要求。在力扣原题子数组最少包含一个元素的约束下两种写法都能过但全负数用例下前缀和版本特别容易因为初始化不当而输出0。后续扩展的灵活性不同。这一点在下一章详细展开。本质上前缀和视角更擅长处理区间端点约束DP 视角更擅长处理结尾元素约束。哪个更好用取决于题目改法。4.4 一个更深刻的等价观察两个算法都在做同一件事把两个算法各自的核心动作提炼出来Kadaneif dp 0: dp 0丢弃负前缀然后dp nums[i]。前缀和if prefix min_so_far: min_so_far prefix丢弃更大的前缀和起点然后ans max(ans, prefix - min_so_far)。dp 0时的重置操作对应的是在某个位置之前找到一个比我当前累积值更低的前缀和。因为当累计和为负时任何未来的正收益都不需要依赖这段负历史。前缀和版本里的min_so_far更新其实就是在持续追踪从哪里开始累积最划算。一旦前缀和比历史最小值还小说明从这个位置再往后看作为起点的潜力更大。想得再直白一点Kadane 是从结尾倒推起点前缀和是从起点正推终点。前者在每个位置问最好的我以这里结尾来自哪里后者在每个位置问以历史最好起点到这里赚了多少。两个问题是一体两面。5. 扩展变式视角不同改造难度天差地别5.1 变式一允许删除一个元素后的最大子数组和这是力扣1186. 删除一次得到子数组最大和的简化思想也常见于面试追问。题目改成你最多可以删除一个元素求剩余子数组的最大和。如果用 DP 视角解法很自然定义两个状态f[i]以 i 结尾且未删除过元素的最大子数组和和g[i]以 i 结尾且已经删除过一个元素的最大子数组和。转移方程f[i] max(nums[i], f[i-1] nums[i]) g[i] max(g[i-1] nums[i], f[i-1]) # 删除 nums[i]或者之前已经删过、现在接着 ans max(f[i], g[i])这个思路很直接因为 DP 状态天然可以携带是否删除过这个附加信息。如果用前缀和视角处理删除一个元素要复杂一些。删除nums[k]本质上是在区间[i, j]里挖掉一个点区间和变成S[j1] - S[i] - nums[k]。要同时优化i、j、k三个变量维护结构要复杂很多需要前缀最大、后缀最大之类的分段信息。所以在这个变式下DP 视角明显更优。5.2 变式二环形数组的最大子数组和力扣918. 环形子数组的最大和是另一个经典扩展。环形数组意味着子数组可以跨越首尾此时有一个著名结论最大环形子数组和 max(普通最大子数组和, 总和 - 普通最小子数组和)。这个结论用前缀和视角理解非常优雅跨越首尾的子数组等价于总区间去掉一段中间的子数组总和减去中间最小子数组和剩下的就是跨越首尾的最大段。求最小子数组和只需要把 Kadane 里所有最大换成最小或者取负数求最大。前缀和视角下总和减去中间最小段的表述就是total - min(子段和)的直接翻译。DP 视角也能做但需要把数组复制一遍然后限制子数组长度不超过 n滑动窗口的复杂度会引入额外状态。相比之下前缀和/区间和的视角更容易推出这个简洁结论。5.3 变式三恰好包含 k 个元素的最大子数组和再换一个改法要求子数组长度恰好为 k求最大和。这个变式有固定套路——滑动窗口或者更精确地说是用前缀和配合限定窗口范围内找最小前缀和for i in range(k, n1): ans max(ans, S[i] - min(S[i-k .. i-1]))这里如果你想用 DP 的以 i 结尾状态会发现长度限制让转移方程变得很难看因为你不能只关心f[i-1]还得知道前一个子数组的长度。而前缀和版本只需要维护一个长度为 k 的窗口内的最小值代码非常干净。所以在这个变式里前缀和视角完胜。5.4 变式对比小结变式DP 视角的改造难度前缀和视角的改造难度建议允许删除一个元素容易加一个状态维度较难要同时优化三个变量用 DP环形数组一般复制数组 限长容易总段 - 最小段用前缀和/区间思维恰好 k 个元素困难状态需要带长度容易窗口内最小前缀和用前缀和结论很清楚不要只记一种解法的模板而要把两种视角都装进脑子里。面试官很喜欢在最大子数组和之后追加一个变式你手里多一个视角就多一条路。6. 刷题实战体会从会做到能吃透的几个建议6.1 我的踩坑记录三个最常见的错误第一次接触这道题时我在前缀和版本上栽过跟头后来教别人的时候也经常看到下面这三类问题第一个坑是min_so_far初始值设置成nums[0]。这个初值会导致第一个元素作为右端点时没有可用的左端点因为左右端点不能重合最终答案会漏掉从第一个元素开始的子数组。正确写法是初始化min_so_far 0把空数组前缀S[0] 0当作起点。当然如果你是先求完整前缀和数组再扫一遍只要循环从i 1开始也能避开这个坑但滚动写法最容易出错。第二个坑是 Kadane 里把ans初始化为0。在数组全为负数时ans 0会让答案错误地变成 0。力扣原题的约束是子数组至少包含一个元素所以全负数场景是合法的必须把ans初始化为nums[0]或者-inf再进入循环。第三个坑是误以为dp的最终值就是答案。前面说过dp表示以当前元素结尾的最优值全局最优可能出现在中间某个位置后续被负数拖累后dp反而变小了。所以必须单独维护ans在每轮更新时同步取max。6.2 我个人偏好的刷题流程面对这种多种解法等价的经典题我建议的复盘顺序不是直接背最优解而是先写暴力 O(n^2)确认自己对区间和的定义没有误解。再用前缀和优化到 O(n^2)枚举区间时 O(1) 求区间和体会区间和 前缀和之差这个恒等式。接着思考能否不枚举所有区间于是引出历史最小前缀和贪心写出 O(n) 前缀和版本。换一种思路从状态转移出发写 Kadane。最后对比两份代码的每一步中间结果发现它们数值一致再去推导恒等式dp_i S[i1] - min(S[0..i])。这五步走完你对这道题的理解深度会远超背十遍题解的人。以后再遇到最大子数组和的任何变式你至少有两条可选的思考路径而不是被单一模板锁死。6.3 从这道题延伸出去动态规划与数据结构的统一我后来在做更多题时发现dp_i S[i1] - min(S[0..i])这个模式不止出现在最大子数组和里。很多看起来毫不相干的题目本质上都在做同一件事在某个线性扫描过程中维护一个历史最优起点然后计算当前状态 - 历史最优起点作为候选答案。比如买卖股票的最佳时机力扣121dp_i prices[i] - min(prices[0..i-1])和最大子数组和的前缀和版本结构一模一样。再比如子数组和为 K 的个数力扣560核心也是前缀和 哈希表只不过把 min 换成了计数。一旦你习惯了当前前缀和 历史前缀信息这种模式你会发现在线性结构上求极值、计数、判断存在性很多都可以统一到前缀和框架下。反过来Kadane 这种以结尾定义状态的 DP 思路也会在最长上升子序列、最大乘积子数组力扣152里反复出现。最大乘积子数组就是 Kadane 的升级版只不过因为负数会把最大变最小、最小变最大你需要同时维护最大和最小两个状态。如果你把最大子数组和的 DP 理解透了152的转移方程几乎是顺理成章。6.4 竞赛场景里的实战建议如果你在打算法竞赛比如信奥、蓝桥杯追求的是最短时间内写对代码。我的建议是如果题目直接是最大子数组和优先写 Kadane。原因是状态定义清晰、初始化简单、边界条件最少写完基本不用验。如果题目带着区间、前缀、环形、长度限制这类修饰词优先往前缀和想因为区间端点约束在前缀和视角下往往有现成的简洁表达。两个写法的复杂度相同都是 O(n)所以不需要担心性能差异。差异只在于你哪个更熟练、哪个对边界处理更有把握。面试场景里我更推荐在纸上把两种写法的推导过程都讲一遍。这能向面试官展示你对问题本质的理解而不是机械记忆模板。你可以先说 Kadane 的状态定义和转移然后补一句其实这个题也可以用前缀和来看每一个 dp 值都等于当前前缀和减历史最小前缀和再画一下两者的对应关系。这个加分项在算法面试中非常明显。最后说一点个人体会我做算法题这些年最大的成长节点往往不是AC 了一道难题而是发现两道看起来完全不同的题其实是同一个模型。最大子数组和这道题恰好是体会这种殊途同归的最佳起点。它能让你同时感受到动态规划的状态视角和前缀和的区间视角如何指向同一个答案。如果你正在刷力扣热题 100建议把这道题当作一题多解的范本花一个晚上把两条推导链彻底走通收益会远超多刷十道简单题。