企业官网建设流程全解析

刷 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] = 0，S[k] = nums[0] + nums[1] + ... + nums[k-1]（这里用S[k]表示前 k 个元素之和，可以让下标计算更清爽）。

那么任意连续子数组nums[i..j]的和可以写成：

sum(nums[i..j]) = S[j+1] - S[i]

其中0 <= i <= j < n。于是题目等价于求：

max_{0 <= i < j' <= n} (S[j'] - S[i])

注意这里j'的取值范围是1..n，i的范围是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 = -1，ans = -1，更新历史最小为 -1
• 走到-3，差值-3 - (-1) = -2，ans 仍为 -1，更新历史最小为 -3
• 走到-6，差值-6 - (-3) = -3，ans 仍为 -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]对应的子数组，它只有两种可能：

1. 单独由nums[i]构成，即k = i，和为nums[i]。
2. 接在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[i+1] - S[k]) = S[i+1] - min_{0 <= k <= i} S[k]

看到没有？“以 i 结尾的最大子数组和” 恰好等于"当前前缀和减去历史最小前缀和"。这个公式把 DP 状态直接翻译成了前缀和语言。

于是 Kadane 算法里的dp更新，就等价于前缀和版本里的prefix - min_so_far；Kadane 算法里的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放在表格里对照：

观察这张表，每一轮的dp和prefix - min_so_far完全相等。这不是巧合，而是由dp_i = S[i+1] - 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 一个更深刻的等价观察：两个算法都在做同一件事

把两个算法各自的核心动作提炼出来：

• Kadane：if 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[j+1] - 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, n+1): ans = max(ans, S[i] - min(S[i-k .. i-1]))

这里如果你想用 DP 的"以 i 结尾"状态，会发现长度限制让转移方程变得很难看，因为你不能只关心f[i-1]，还得知道前一个子数组的长度。而前缀和版本只需要维护一个长度为 k 的窗口内的最小值，代码非常干净。所以在这个变式里，前缀和视角完胜。

5.4 变式对比小结

结论很清楚：不要只记一种解法的模板，而要把两种视角都装进脑子里。面试官很喜欢在最大子数组和之后追加一个变式，你手里多一个视角，就多一条路。

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 我个人偏好的刷题流程

面对这种"多种解法等价"的经典题，我建议的复盘顺序不是直接背最优解，而是：

1. 先写暴力 O(n^2)，确认自己对"区间和"的定义没有误解。
2. 再用前缀和优化到 O(n^2)（枚举区间时 O(1) 求区间和），体会"区间和 = 前缀和之差"这个恒等式。
3. 接着思考：能否不枚举所有区间？于是引出"历史最小前缀和"贪心，写出 O(n) 前缀和版本。
4. 换一种思路，从状态转移出发写 Kadane。
5. 最后对比两份代码的每一步中间结果，发现它们数值一致，再去推导恒等式dp_i = S[i+1] - min(S[0..i])。

这五步走完，你对这道题的理解深度会远超背十遍题解的人。以后再遇到"最大子数组和"的任何变式，你至少有两条可选的思考路径，而不是被单一模板锁死。

6.3 从这道题延伸出去：动态规划与数据结构的统一

我后来在做更多题时发现，dp_i = S[i+1] - min(S[0..i])这个模式不止出现在最大子数组和里。很多看起来毫不相干的题目，本质上都在做同一件事：在某个线性扫描过程中，维护一个"历史最优起点"，然后计算"当前状态 - 历史最优起点"作为候选答案。

比如买卖股票的最佳时机（力扣121）：dp_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，建议把这道题当作"一题多解"的范本，花一个晚上把两条推导链彻底走通，收益会远超多刷十道简单题。