刷 LeetCode 152「最大乘积子数组」的时候我经常在评论区看到这样的疑问这题明明标注着“动态规划”为什么题解代码里连个 dp 数组都没有为什么也没看到dp[0] something这种初始化是不是写错了没写错。你看到的大多数版本其实用了“滚动变量”把 dp 数组空间优化掉了只留下两个变量cur_max和cur_min在那儿互相更新。换句话说这题确实是货真价实的线性动态规划只是大家习惯把空间复杂度从 O(n) 压到 O(1)于是“dp 数组”就隐身了初始化自然也跟着隐身了。这篇文章就把这件事彻底讲透先还原题目从朴素思路一路推导出标准 DP 状态设计再重点回答“为什么不初始化 dp 数组”最后把完整代码、手推用例、常见坑位都整理出来。刚开始刷动态规划、被各种模板绕晕的朋友顺着下面的思路一步步推这题就能真正吃透而不是只会背代码。1. 先搞清楚这题到底是不是“标准动态规划”1.1 题目在问什么题目本身很短给你一个整数数组nums找出数组中乘积最大的非空连续子数组返回这个子数组对应的乘积。“非空”“连续”是两个硬条件也就是说必须至少取一个数而且不能跳着选。三个典型例子先摆出来后面手推还会反复用到它们输入输出解释[2, 3, -2, 4]6子数组 [2, 3] 乘积最大[-2, 0, -1]0任何跨过 0 的子数组乘积都是 0 或负数[-2, 3, -4]24整个数组乘起来才是最大约束条件里有一项很容易被忽略数组长度至少为 1。这直接决定了初始化写法里ans nums[0]是安全的不用处理空数组的边界。1.2 为什么“最大和”的套路在这里失效很多人的第一反应是套最大子数组和的 Kadane 算法核心就一句cur max(cur x, x)。这个算法对加法成立是因为加法是单调的——当前和越大往后加出来的结果也越大所以只需要维护一个“当前最大值”滚动下去。乘法完全不是这么回事。乘一个负数会把大小关系整个颠倒过来原本很小的负数乘完负数反而可能变成很大的正数原本很大的正数乘完负数反而变成很小的负数。更别提 0 了任何前缀乘到 0 立刻归零最优延续当场断掉。拿 [-2, 3, -4] 验证一下如果照搬最大和的思路cur -2cur max(3, -2 3) 3cur 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 的vectorint 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]、dp[2]转移读取前两个状态循环从 3 开始最长上升子序列必须把 dp[i] 全初始化为 1每个元素自身就是长度为 1 的上升子序列最大子数组和只初始化 dp[0]中间状态先写后读最大乘积子数组只初始化 f[0]、g[0]中间状态先写后读编辑距离必须初始化表格第一行、第一列后续格子要读取左上左三个邻居背包问题必须初始化 dp[0]容量 0 是转移的起点其余 0 或 -inf 看问题定义表格里最容易被新手记反的是最长上升子序列——它的 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 ansC 版本几乎一模一样适合面试手写class Solution { public: int maxProduct(vectorint 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 2cur_min 2ans 2。inums[i]操作cur_maxcur_minans02初始22213正数不交换cur_max max(3, 6) 6cur_min min(3, 6) 36362-2负数交换cur_max 3cur_min 6再算 cur_max max(-2, -6) -2cur_min min(-2, -12) -12-2-12634正数不交换cur_max max(4, -8) 4cur_min min(4, -48) -484-486注意看 i2 那一行。交换之后原来最大的 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。inums[i]操作cur_maxcur_minans100 非负不交换cur_max max(0, -2×0) 0cur_min min(0, -2×0) 00002-1负数交换后仍都是 0cur_max max(-1, 0) 0cur_min min(-1, 0) -10-100 把前面的乘积全部清零任何跨越它的前缀子数组都不可能成为最大候选所以答案定格在 0。很多题解说“遇到 0 要重置 cur 为 1”本质上就是这个逻辑的另类表达。用例三 [-2, 3, -4] 则是负数翻转的“高光时刻”。初始cur_max cur_min ans -2。inums[i]操作cur_maxcur_minans13正数不交换cur_max max(3, -6) 3cur_min min(3, -6) -63-632-4负数交换cur_max -6cur_min 3再算 cur_max max(-4, 24) 24cur_min min(-4, -12) -1224-1224第二轮交换之后前一轮的最小值 -6 乘上 -4 变成了 24一举刷新答案。这就是为什么“只维护最大值”一定会错——没有最小值做后手你根本等不到这个翻转时刻。3.4 复杂度与边界条件时间上只扫描了一遍数组是 O(n)空间上只用了三个变量是 O(1)。这也是滚动变量优化最直观的收益。边界条件清单数组长度恰好为 1循环不执行直接返回nums[0]正确数组全正数cur_max一路变大cur_min一路也变大ans最终等于全部元素乘积正确数组全负数每次都要交换但交换本身不产生额外分支照常工作数组含 00 把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 排查技巧速查表症状可能原因检查点含负数的用例结果偏小只维护了最大值代码里有没有 min 状态或交换逻辑全负数数组答案是 1 或 0ans 初始化错误ans 是否等于 nums[0]结果忽大忽小不稳定更新顺序串味是否用了临时变量是否先交换再乘结果等于某一子段但不是最大返回了 f[n-1]最后是否返回 max(f)而不是 f 末位含 0 的用例结果偏大没有正确处理 0 的重置检查 max/min 公式里是否包含了 nums[i] 本身我给新人的调试建议很土但很有效写一个 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 面试时怎么把这道题讲清楚面试遇到这题我建议按下面五步讲有条理又不会踩空先说暴力思路枚举所有起点和终点时间复杂度 O(n^2)作为铺垫讲状态定义f[i]是以 i 结尾的最大乘积g[i]是以 i 结尾的最小乘积解释为什么需要两个状态负数会让最大最小互换举 [-2, 3, -4] 当例子给出转移公式和代码说明ans要记录历史峰值而不能返回f[n-1]最后补一句空间优化因为状态只依赖前一项所以滚动成两个变量空间降到 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 一步一步算出来你才能真正看见“负数翻转”是怎么发生的。画出那一瞬间的感觉比任何讲解都值钱。之后再去优化、去变式、去刷题都会轻松很多。