企业官网建设流程全解析

刷 LeetCode 152「最大乘积子数组」的时候，我经常在评论区看到这样的疑问：这题明明标注着“动态规划”，为什么题解代码里连个 dp 数组都没有？为什么也没看到dp[0] = something这种初始化？是不是写错了？

没写错。你看到的大多数版本，其实用了“滚动变量”把 dp 数组空间优化掉了，只留下两个变量cur_max和cur_min在那儿互相更新。换句话说，这题确实是货真价实的线性动态规划，只是大家习惯把空间复杂度从 O(n) 压到 O(1)，于是“dp 数组”就隐身了，初始化自然也跟着隐身了。

这篇文章就把这件事彻底讲透：先还原题目，从朴素思路一路推导出标准 DP 状态设计，再重点回答“为什么不初始化 dp 数组”，最后把完整代码、手推用例、常见坑位都整理出来。刚开始刷动态规划、被各种模板绕晕的朋友，顺着下面的思路一步步推，这题就能真正吃透，而不是只会背代码。

1. 先搞清楚：这题到底是不是“标准动态规划”

1.1 题目在问什么

题目本身很短：给你一个整数数组nums，找出数组中乘积最大的非空连续子数组，返回这个子数组对应的乘积。“非空”“连续”是两个硬条件，也就是说必须至少取一个数，而且不能跳着选。

三个典型例子先摆出来，后面手推还会反复用到它们：

约束条件里有一项很容易被忽略：数组长度至少为 1。这直接决定了初始化写法里ans = nums[0]是安全的，不用处理空数组的边界。

1.2 为什么“最大和”的套路在这里失效

很多人的第一反应是套最大子数组和的 Kadane 算法，核心就一句：cur = max(cur + x, x)。这个算法对加法成立，是因为加法是单调的——当前和越大，往后加出来的结果也越大，所以只需要维护一个“当前最大值”滚动下去。

乘法完全不是这么回事。乘一个负数会把大小关系整个颠倒过来：原本很小的负数，乘完负数反而可能变成很大的正数；原本很大的正数，乘完负数反而变成很小的负数。更别提 0 了，任何前缀乘到 0 立刻归零，最优延续当场断掉。

拿 [-2, 3, -4] 验证一下，如果照搬最大和的思路：

• cur = -2
• cur = max(3, -2 + 3) = 3
• cur = max(-4, 3 + (-4)) = -1

最后答案是 3，可真正的最大乘积是 (-2)×3×(-4) = 24。差了整整 8 倍。这个例子你应该记下来，后面所有“为什么要维护最小值”的解释都会回到它。

1.3 两个状态的设计：最大与最小必须同时跟踪

动态规划解决问题的第一步永远是定义状态。对于这道题，最自然的状态定义是：

• f[i]：以nums[i]结尾的子数组的最大乘积；
• g[i]：以nums[i]结尾的子数组的最小乘积。

“以 i 结尾”这个限定非常关键。它保证了子数组是连续的，也保证了子数组一定包含nums[i]，所以不会出现“空的延续”。

那么f[i]可能从哪来？只有三种来源：一是从nums[i]重新开始，只有它自己；二是接在f[i-1]后面，即f[i-1] * nums[i]；三是接在g[i-1]后面，即g[i-1] * nums[i]。第三种情况正是前面说的“负数翻转”——如果nums[i]是负数，之前乘积最小的子数组接上它，反而可能变成乘积最大的。

把三种来源统一起来，转移式可以写成很干净的形式：

a = f[i-1] * nums[i] b = g[i-1] * nums[i] f[i] = max(nums[i], a, b) g[i] = min(nums[i], a, b)

这里有个很容易踩的细节：a和b必须先用临时变量存下来。因为f[i]和g[i]的转移都依赖它们各自的前一个状态，如果你先更新了f[i]，再用更新后的f[i]去算g[i]，整个状态就串味了。这个坑后面第 4 节还会详细说。

1.4 为什么说它是“线性 DP”

f[i]只依赖f[i-1]和g[i-1]，一趟从左到右的扫描就能把所有状态算完，这就是线性动态规划（Linear DP）的典型特征。它和最大子数组和、打家劫舍、爬楼梯属于同一个家族，骨骼都一样：定义“以 i 结尾”的状态，找转移关系，处理边界起点，然后线性扫描。

这也是刷题社区里常把它和洛谷动态规划题单中的 P1115 最大子段和放在一起对比的原因。P1115 是只维护一个状态的线性 DP，这道题是维护两个状态的线性 DP，对比着刷一次，你对“状态数量由什么决定”的理解会比单独刷十题都深。

2. 核心答疑：为什么看不到 dp 数组初始化

2.1 教科书版是初始化了的，只是只初始化边界

先把“不优化”的完整版写出来，看看 dp 数组版到底长什么样：

def max_product_subarray(nums): n = len(nums) f = [0] * n g = [0] * n f[0] = g[0] = nums[0] ans = nums[0] for i in range(1, n): a = f[i - 1] * nums[i] b = g[i - 1] * nums[i] f[i] = max(nums[i], a, b) g[i] = min(nums[i], a, b) ans = max(ans, f[i]) return ans

看清楚了吗？它其实有初始化，只是只初始化了两个边界：f[0] = g[0] = nums[0]。剩下的f[1]到f[n-1]、g[1]到g[n-1]全部没有刻意初始化。

为什么不初始化？因为在这个自底向上的循环里，每一轮都是先给f[i]、g[i]赋值，之后才可能读取它们。换句话说，任何下标在被读取之前，已经被新值覆盖了。这就是计算机里常见的“先写后读”原则——只要保证读之前必然有写，那初始值是什么都无所谓，哪怕是垃圾值也会被瞬间覆盖掉。

2.2 语言层面的一个小补充

聊到数组初始化的同学，这里顺便多说一句。Python 的[0] * n、C++ 的vector<int> dp(n)都会先把数组填成确定值（0），所以你就算忘了先写后读，读到的也是 0 而不是野值，程序不一定崩，但结果可能悄悄错。

C 语言就不一样了，int *dp = malloc(n * sizeof(int))完全不初始化，里面是随机的垃圾数据。但在上面这种“先写后读”的逻辑下，C 语言也可以合法地跳过初始化，只要你能保证每个元素第一次被读之前一定被赋过值。很多从 C 写过来的人习惯了 malloc 后立刻 memset，放到 DP 里其实没必要——边界初始化那一下是必须的，中间状态真的可以偷懒。

2.3 滚动变量：dp 数组被空间压缩优化掉了

回到你要问的核心。既然f[i]只依赖f[i-1]和g[i-1]，g[i]同理，那么当整趟循环跑完时，我们真正关心的只有所有f[i]里的最大值，而不是中间每一个历史状态。这就允许我们不开整个数组，只用两个变量滚动前进。

def max_product_subarray(nums): cur_max = cur_min = ans = nums[0] for i in range(1, len(nums)): if nums[i] < 0: cur_max, cur_min = cur_min, cur_max cur_max = max(nums[i], cur_max * nums[i]) cur_min = min(nums[i], cur_min * nums[i]) ans = max(ans, cur_max) return ans

这段代码里依然有“初始化”：cur_max = cur_min = ans = nums[0]。它们本质上就是f[0]、g[0]和答案的初值。所以最严谨的说法是：没有初始化的是 dp 数组的中间位置，边界位置的初始化一直存在，而且直接决定程序正确性。

if nums[i] < 0: cur_max, cur_min = cur_min, cur_max这一行就是赫赫有名的“负数翻转”交换。它的原理是：当nums[i]是负数时，f[i-1] * nums[i]会变成最小值候选，g[i-1] * nums[i]会变成最大值候选，所以先把两个滚动变量对调，再统一套用“取 max / 取 min”的公式，就等价于前面第 1 节里分三种情况讨论的完整公式。这样写代码更短，也更不容易在分支里漏掉nums[i] == 0的情况。

2.4 另一派“初始化为 1”的写法，为什么也能过

网上还有一大批题解把cur_max、cur_min初始化为 1，然后从第 0 个元素开始遍历：

cur_max = cur_min = 1 ans = nums[0] for x in nums: if x < 0: cur_max, cur_min = cur_min, cur_max cur_max = max(x, cur_max * x) cur_min = min(x, cur_min * x) ans = max(ans, cur_max) return ans

初始化为 1 的理由是乘法的单位元——任何数乘 1 等于它自己，相当于在数组前面虚拟了一个“空乘积”。这样第 0 个元素也能走同一套更新逻辑，不用单独写边界。

但这个写法有两个大坑。第一，ans绝不能也初始化为 1。全负数数组 [-1, -2] 的最大乘积明明是 2，如果ans = 1，答案会错成 1，因为你把“不取任何元素的空子数组乘积为 1”这个本不存在的选项也算进去了。题目明确要求子数组非空，所以ans必须等于nums[0]，或者用负无穷再在循环里兜底。第二，理解上容易让人以为 1 是“安全初始值”，一旦哪天改成别的运算（比如加法），这个直觉就会带偏你。

2.5 什么时候必须初始化 dp 数组，什么时候可以偷懒

把上面的经验总结成一句判断标准就够用了：

如果某个状态在被赋值之前就可能被读取，就必须初始化；如果每一次读取之前它都一定被新值覆盖，就可以跳过初始化。

举几个经典题对照一下：

表格里最容易被新手记反的是最长上升子序列——它的 dp 数组初始化是“全部初始化为 1”，而不是只初始化边界。为什么呢？因为 LIS 的转移dp[i] = max(dp[j] + 1)依赖的是所有j < i的状态，而不仅仅是前一个状态，所以不能滚动到 O(1)，也不能偷懒只处理边界。状态依赖的范围，决定了你能做的空间压缩程度，也决定了初始化的形式。这条规律可以套用到几乎所有线性 DP 题目上。

3. 完整编码与手推验证：一步不落

3.1 可以直接抄的 Python / C++ 版本

滚动变量版的最终代码，我建议理解之后背着写一遍，而不是直接复制。注释我给你标好了关键转折点：

def max_product_subarray(nums): # f[0]、g[0] 的边界初始化，同时也是答案初值 cur_max = cur_min = ans = nums[0] for i in range(1, len(nums)): # 负数翻转：乘负数会把最大值候选和最小值候选对调 if nums[i] < 0: cur_max, cur_min = cur_min, cur_max # 统一的转移：要么从 nums[i] 重新开始，要么延续之前的最大/最小乘积 cur_max = max(nums[i], cur_max * nums[i]) cur_min = min(nums[i], cur_min * nums[i]) # 最大乘积子数组可能结束在任意位置，所以答案要持续更新 ans = max(ans, cur_max) return ans

C++ 版本几乎一模一样，适合面试手写：

class Solution { public: int maxProduct(vector<int>& nums) { int curMax = nums[0], curMin = nums[0], ans = nums[0]; for (int i = 1; i < nums.size(); ++i) { if (nums[i] < 0) { swap(curMax, curMin); } curMax = max(nums[i], curMax * nums[i]); curMin = min(nums[i], curMin * nums[i]); ans = max(ans, curMax); } return ans; } };

两个版本核心完全一致：边界初始化nums[0]，负数交换，统一更新，答案跟踪。

3.2 手推用例一：[2, 3, -2, 4]

我们拿最经典的例子逐轮推一遍。初始：cur_max = 2，cur_min = 2，ans = 2。

注意看 i=2 那一行。交换之后，原来最大的 6 变成了 cur_min 去乘 -2，得到了 -12；原来最小的 2 变成了 cur_max 去乘 -2，得到 -2。这一步就是整个算法的精髓：负数出现时，前一轮的“最大”要退居二线，“最小”反而有机会创造奇迹。

最后ans = 6，正确答案也是 6（子数组 [2, 3]）。特别强调一下最后一行：循环结束时cur_max = 4，但答案不是 4，因为最大乘积子数组 [2, 3] 并没有延伸到最后一个元素。这就是为什么必须用ans记录历史峰值，而不能直接返回cur_max。这个错误我在新手眼里见过不下十次。

3.3 手推用例二：[-2, 0, -1] 和三：[-2, 3, -4]

用例二用来验证 0 的“重置”效果。初始：cur_max = cur_min = ans = -2。

0 把前面的乘积全部清零，任何跨越它的前缀子数组都不可能成为最大候选，所以答案定格在 0。很多题解说“遇到 0 要重置 cur 为 1”，本质上就是这个逻辑的另类表达。

用例三 [-2, 3, -4] 则是负数翻转的“高光时刻”。初始：cur_max = cur_min = ans = -2。

第二轮交换之后，前一轮的最小值 -6 乘上 -4 变成了 24，一举刷新答案。这就是为什么“只维护最大值”一定会错——没有最小值做后手，你根本等不到这个翻转时刻。

3.4 复杂度与边界条件

时间上只扫描了一遍数组，是 O(n)；空间上只用了三个变量，是 O(1)。这也是滚动变量优化最直观的收益。

边界条件清单：

• 数组长度恰好为 1：循环不执行，直接返回nums[0]，正确；
• 数组全正数：cur_max一路变大，cur_min一路也变大，ans最终等于全部元素乘积，正确；
• 数组全负数：每次都要交换，但交换本身不产生额外分支，照常工作；
• 数组含 0：0 把cur_max和cur_min归零，等价于“重新开始”，正确。

4. 常见错误与排查实录：踩过的坑都在这

4.1 错误一：只维护一个 cur_max，照搬最大和

# 错误示范 cur = ans = nums[0] for i in range(1, len(nums)): cur = max(nums[i], cur * nums[i]) ans = max(ans, cur) return ans

这个代码跑 [-2, 3, -4] 会得到 3，正确答案是 24。原因前面讲过：单变量无法感知“最小值乘负数变最大值”的翻转。判断自己是不是犯了这类错误，只要看代码里有没有cur_min或者交换变量。没有的话，这题基本必错。

4.2 错误二：ans 初始化为 1 或 0

# 错误示范 cur_max = cur_min = ans = 1

跑 [-1, -2]，输出 1，正确答案是 2。原因：1 是乘法单位元，它代表了一个“空子数组”的乘积，而题目要求子数组必须非空。同理，ans初始化为 0 也不对，因为最大乘积有可能是负数，比如 [-5] 的答案是 -5，初始化 0 会让答案永远不小于 0。

正确的做法永远是ans = nums[0]。如果用了“从 1 开始遍历”的流派，ans仍然要取nums[0]，或者取-float('inf')然后在循环里第一次遇到元素时兜底更新。

4.3 错误三：不使用临时变量，导致状态被串改

看这个“不交换流派”的错误版本：

# 错误示范：先更新 cur_max 再更新 cur_min for i in range(1, len(nums)): cur_max = max(nums[i], cur_max * nums[i], cur_min * nums[i]) cur_min = min(nums[i], cur_max * nums[i], cur_min * nums[i])

第二行算cur_min时，cur_max已经是新值了。本来cur_min应该依赖旧的cur_max和旧的cur_min，现在右边混进了一个当前轮的新值，状态转移就不再是“从前一轮而来”。这种 bug 跑单个测试用例很难一次暴露，但遇到nums[i] < 0的组合时结果就会错得莫名其妙。

正确写法是把两个乘积先算出来，或者干脆用“负数交换”流派：

# 正确写法：先存临时变量 a = cur_max * nums[i] b = cur_min * nums[i] cur_max = max(nums[i], a, b) cur_min = min(nums[i], a, b)

4.4 错误四：直接返回 f[n-1] 而不是历史最大值

# 错误示范（数组版） return f[n - 1]

跑 [2, 3, -2, 4]，f[3]是以 4 结尾的最大乘积，也就是 4，但正确答案是 6。原因是我们定义的状态是“以 i 结尾”，而最大乘积子数组不必结束在最后一个位置，它可能中途就出现了。所以必须全程维护一个ans = max(ans, f[i])，最后返回的是这个历史峰值，不是最后一个状态。这个错误和最大子数组和那题一模一样，很多人在两个题里各踩一次。

4.5 排查技巧速查表

我给新人的调试建议很土但很有效：写一个 O(n^2) 的暴力版本，随机生成几组包含正、负、0 的小数组，让暴力版本和 DP 版本对拍。数据量小、迭代次数多，对拍个几十轮，所有上面这些 bug 都会现形。刷题初期花十分钟做这件事，比看十篇题解都顶用。

5. 延伸：空间压缩的通用套路与面试表达

5.1 “滚动”不止用在最大乘积子数组

把这道题的优化思路抽象出来，是一条通用的空间压缩心法：状态转移里只用到前 k 个状态，就可以用 k 个变量滚动，把保存全部历史的数组砍掉。

• 斐波那契数列常用三个变量滚动，替代整个 dp 数组；
• 爬楼梯可以用两个变量滚动；
• 最大子数组和用一个cur滚动；
• 最大乘积子数组因为要“最大 + 最小”两个状态，所以用两个变量滚动。

再往深处走一步：二维 DP 滚动成一维时，遍历顺序往往要反转。最典型的是 0/1 背包，二维dp[i][j]依赖dp[i-1][j]和dp[i-1][j-w]，滚动成一维后必须倒序枚举容量，否则会用掉本轮刚更新过的值，相当于每个物品被重复选。这类“滚动方向”问题，本质上和前面“先存临时变量再更新”是一个道理，都是怕新旧状态混在一起。

5.2 变式题与进阶练习

如果你把这题吃透了，有几个变式可以顺手练一练：

• 返回最大乘积子数组本身，而不只是乘积。思路是在更新cur_max和ans时同时记录区间起点、终点，答案刷新时把起止位置也一起更新。实现上比原题多两个变量，但逻辑是一样的。
• 求乘积为正数的最长子数组长度。这题状态要从“最大/最小乘积”扩展成“最长正乘积长度、最长负乘积长度”，状态数量从 2 变 2，但要处理符号和长度，转移更绕。
• 环形数组版本的最大乘积。环形问题通常采用“破环为链”或者分类讨论（答案要么在直线上，要么跨越边界），配合这道题的双状态，难度会明显上一个台阶。

练习资源上，洛谷动态规划题单里 P1115 最大子段和是单状态的对应题，P1020 导弹拦截包含 LIS 和最长不上升子序列两个经典转移，P1280 尼克的任务是线性 DP 的另一种题型。把这几个题连起来刷一遍，你对线性 DP 的理解会非常扎实。

5.3 面试时怎么把这道题讲清楚

面试遇到这题，我建议按下面五步讲，有条理又不会踩空：

1. 先说暴力思路：枚举所有起点和终点，时间复杂度 O(n^2)，作为铺垫；
2. 讲状态定义：f[i]是以 i 结尾的最大乘积，g[i]是以 i 结尾的最小乘积；
3. 解释为什么需要两个状态：负数会让最大最小互换，举 [-2, 3, -4] 当例子；
4. 给出转移公式和代码，说明ans要记录历史峰值而不能返回f[n-1]；
5. 最后补一句空间优化：因为状态只依赖前一项，所以滚动成两个变量，空间降到 O(1)。

面试官如果追问“为什么不用初始化 dp 数组”，你就可以回答：边界状态f[0]、g[0]已经初始化了，中间状态都是先写后读，旧值不会被读取，所以不需要额外初始化；更进一步，滚动变量的写法让 dp 数组本身都不存在了。

最后说点我个人带人刷题时的体会。很多新手卡在这题上，不是因为不懂“最大乘积”的概念，而是太执着于“dp 数组长什么样”。其实动态规划是状态定义和转移关系，不是数据结构形式。你完全可以把cur_max、cur_min就当成f[i]、g[i]在 i 时刻的投影——这题用变量还是用数组，只是空间换时间的代价选择，而这道题恰好不需要用空间换时间罢了。

按我自己的经验，第一次学这题别急着看代码，拿 [−2, 3, −4] 和 [2, 3, −2, 4] 各画一张手推表，把 cur_max、cur_min 一步一步算出来，你才能真正看见“负数翻转”是怎么发生的。画出那一瞬间的感觉，比任何讲解都值钱。之后再去优化、去变式、去刷题，都会轻松很多。