这道题我第一次在面试里遇到时差点就在“只维护一个最大值”的坑里出不来了。乘积子数组和加法子数组最大的区别在于负数——一个很小的负数乘上另一个负数可能瞬间翻身成为最大值。LeetCode 152 考察的就是如何在数组元素可正可负可零的情况下找到乘积最大的连续子数组。网上关于这题的题解很多但大多直接甩一个max/min双状态转移公式就结束了很少解释清楚“为什么必须同时维护最小值”。这篇我把动态规划的推导过程、三种 Java 写法的演进、零和负数的边界陷阱全部摊开讲争取让基础一般的同学也能一次性吃透。1. 为什么“最大子序和”的套路在这里直接翻车很多人在做这道题之前大概率刷过第 53 题“最大子序和”。那题的 DP 状态转移非常简洁dp[i] max(nums[i], dp[i-1] nums[i])只需要维护一个“加”的状态因为加法里负数是累赘越加越小果断扔掉就行。但乘积完全不同。看一个具体例子nums [-2, 1, -3]如果照搬加法 DP只维护“以当前元素结尾的最大乘积”过程会是这样i 0max -2i 1max max(1, -2 * 1) 1i 2max max(-3, 1 * -3) -3最后得出结果是-3可实际上(-2) * 1 * (-3) 6才是正确答案。问题出在哪在加法中前一个状态越小对当前越不利但在乘法中前一个状态可能很小甚至是很负一旦乘上当前的负数就反转成极大的正数。拿上面的例子来说i 2时最优解不是“以 2 结尾的子数组”而是“从 0 开始到 2 结束的整个子数组”它需要用到i 1时刻的最小值-2。这就是本题和加法子序和的根本区别你缺的不是最大值而是最小值。缺了最小值你就永远不知道“负负得正”的翻盘机会在后头等着。如果把状态定义改成“以i结尾的子数组的最大值”但我们额外再记一个“以i结尾的子数组的最小值”那么当遍历到负数时用最小值去乘就能把反转的机会抓住。这个观察是整道题的钥匙。加法和乘法的另一个差异是零。加个零最多不变乘个零会让之前积累的乘积直接清零。所以遇到零时不能简单把历史最大值传递下去而要“断掉重来”。这引出 DP 状态设计下一个核心问题状态到底怎么定义才不会丢信息。2. 动态规划核心为什么必须同时维护“最大”和“最小”两个状态我们定义两个数组fmax[i]以nums[i]结尾的连续子数组的最大乘积fmin[i]以nums[i]结尾的连续子数组的最小乘积注意这个“结尾”定义它意味着子数组必须包含nums[i]。这一点和“全局最大”不同但正是它能递推的关键——因为以i结尾的状态只需要看i - 1结尾的状态怎么转移过来。转移时fmax[i]可能来自三种情况nums[i]自己单独成为一个子数组比如前面的乘积是负数且很小当前数是非负数重新开始往往更好nums[i] * fmax[i-1]前一个状态是正数且越大越好nums[i] * fmin[i-1]前一个状态是负数当前数也是负数负负得正。fmin[i]的三种情况正好对称nums[i]自己单独成为一个子数组nums[i] * fmin[i-1]nums[i] * fmax[i-1]。所以转移公式写成fmax[i] max(nums[i], nums[i] * fmax[i-1], nums[i] * fmin[i-1]) fmin[i] min(nums[i], nums[i] * fmax[i-1], nums[i] * fmin[i-1])很多人看到这个公式第一反应是fmax的转移里怎么会用到fmin因为我们是在“穷举开头”从i向前回溯时任何一个连续子数组都可以看作“前面一段 当前元素”。前面那段要么取最优最大或最小要么空。对于乘积来说前面一段的符号和大小共同决定结果所以最大和最小都要尝试。这里顺便纠正一个常见误解fmin[i]不是给最终答案用的它自己本身没有“意义”它存在的唯一价值就是为了在i 1遇到负数时能派上用场。这也是代码里min不能省的原因省略任何一个状态递推链就断了。下面用一个带零的例子完整手推一遍确保逻辑没有含糊之处。假设nums [2, 3, -2, 4, -1]i 0, nums[0] 2fmax[0] 2fmin[0] 2i 1, nums[1] 3fmax[1] max(3, 3*2, 3*2) 6fmin[1] min(3, 3*2, 3*2) 3此时全正最大最小都是连续乘i 2, nums[2] -2fmax[2] max(-2, -2*6, -2*3)-2*3 -6-2*6 -12所以fmax[2] -2fmin[2] min(-2, -12, -6) -12i 3, nums[3] 4fmax[3] max(4, 4*(-2), 4*(-12)) 4fmin[3] min(4, -8, -48) -48i 4, nums[4] -1fmax[4] max(-1, -1*4, (-1)*(-48))(-1)*(-48) 48终于反转成功fmin[4] min(-1, -4, 48) -4全局最大值在fmax[0..4]里取max答案是48即2*3*(-2)*4*(-1)。验证无误。注意i 3时fmax[3] 4而不是更大的正数因为-2*4 -8连乘到 4 时前面积累的是负的当前正数反而不能接续。这说明**“以 i 结尾的最大”不需要是全局最大**它可能暂时缩水但只要保住了fmin未来就有机会反超。3. 三种 Java 写法从完整数组到滚动变量再到哨兵技巧有了状态定义和转移公式写代码只是时间问题。下面给出三种实现复杂度从O(n)空间逐步降到O(1)最后一种还能省去对nums[i]单独取max的重复代码。3.1 写法一完整 DP 数组最直观这是最容易照着公式写的版本class Solution { public int maxProduct(int[] nums) { int n nums.length; int[] fmax new int[n]; int[] fmin new int[n]; fmax[0] nums[0]; fmin[0] nums[0]; int ans nums[0]; for (int i 1; i n; i) { fmax[i] Math.max(nums[i], Math.max(nums[i] * fmax[i - 1], nums[i] * fmin[i - 1])); fmin[i] Math.min(nums[i], Math.min(nums[i] * fmax[i - 1], nums[i] * fmin[i - 1])); ans Math.max(ans, fmax[i]); } return ans; } }优点是和公式一一对应适合在面试中先写出正确性显然的版本然后再说“我们优化一下空间”。缺点是开了两个长度为n的数组很多语言下还会互相引用其实没有必要。3.2 写法二滚动变量空间 O(1)仔细观察转移公式i时刻的状态只依赖i-1时刻的状态所以可以用两个变量滚动更新。class Solution { public int maxProduct(int[] nums) { int fmax nums[0]; int fmin nums[0]; int ans nums[0]; for (int i 1; i n; i) { int maxCandidate1 nums[i] * fmax; int maxCandidate2 nums[i] * fmin; fmax Math.max(nums[i], Math.max(maxCandidate1, maxCandidate2)); fmin Math.min(nums[i], Math.min(maxCandidate1, maxCandidate2)); ans Math.max(ans, fmax); } return ans; } }这里有一个非常容易踩的坑fmax和fmin必须先分别用旧的fmax、fmin算出候选值再统一更新。如果写成fmax Math.max(nums[i], Math.max(nums[i] * fmax, nums[i] * fmin)); fmin Math.min(nums[i], Math.min(nums[i] * fmax, nums[i] * fmin));第二行使用的fmax已经是更新后的新值了结果会完全错乱。所以我上面特意先把两个候选值存进局部变量再赋值就是为了避免这种“先更新后使用”的隐患。这也是这个滚动版本最容易 bug 的地方面试时值得主动提一句反而能加分。3.3 写法三先交换后计算代码更紧凑如果nums[i]是负数乘法的效果相当于交换“最大”和“最小”的角色。利用这个性质可以先把两个变量交换再统一乘以nums[i]最后取max/min时就不需要再考虑和nums[i]单独比较了因为乘完 1 倍就是nums[i]。class Solution { public int maxProduct(int[] nums) { int fmax nums[0]; int fmin nums[0]; int ans nums[0]; for (int i 1; i nums.length; i) { if (nums[i] 0) { int tmp fmax; fmax fmin; fmin tmp; } fmax Math.max(nums[i], nums[i] * fmax); fmin Math.min(nums[i], nums[i] * fmin); ans Math.max(ans, fmax); } return ans; } }这个写法的逻辑链条是前一个状态的最大和最小在乘以负数后身份互换互换后再分别乘当前数得到新的最大和最小。理解了这个原理代码就能少写两个Math.max嵌套视觉上也好很多。三种写法的时间复杂度都是O(n)空间复杂度前一种是O(n)后两种是O(1)。实际测试中滚动变量版本的吞吐量没有本质提升因为 DP 本身就是线性扫描真正的瓶颈在 IO 和循环开销。选哪一种主要看你是“优先正确性”还是“优先简洁”。我给一道中等难度的题目列出三种写法的场景建议场景推荐写法理由面试初稿完整 DP 数组和公式对应最直接不容易出错面试优化滚动变量展示空间优化意识复杂度无变化短代码风格 / 竞赛交换法逻辑最紧凑但不建议不熟悉时硬背我再补充一点个人经验如果面试官问“还能不能再优化”不要只回答空间 O(1)还可以提“是否可以一次遍历同时得出最大和最小是否可以把ans初始化为Integer.MIN_VALUE而不是nums[0]”。这两种边界处理方式都能体现你对细节的把控。4. 零和负数的边界处理以及“连续子数组”的隐含要求这道题最容易让测试用例“阴沟翻船”的就是零。看一个例子nums [-2, 0, -1]如果脑子里只有“最大/最小”而没意识到零的作用可能出现两个错误答案只维护最大且遇到负号就交换但没把零当作“重启点”会算出-1 * 0 * -2 0之类的结果或者错误认为“既然遇到负数要交换那遇到零也应该交换”零会整个重置。正确的答案是0[-2, 0]或[0]或[0, -1]的乘积。我们再手推一遍看 DP 为什么自然处理了这个情况i 0, nums[0] -2fmax -2fmin -2i 1, nums[1] 0候选是0 * -2 0所以fmax max(0, 0) 0fmin min(0, 0) 0i 2, nums[2] -1fmax max(-1, -1 * 0) 0fmin min(-1, -1 * 0) -1最终ans max(-2, 0, 0) 0正确。关键点在于遇到 0 时fmax和fmin都会归到 0但下一次状态选择max(nums[i], nums[i] * 0)时如果nums[i]是正的它会选择nums[i]自己重新开始如果nums[i]是负的它也会选择nums[i]自己。这样零后面的连续正数就可以从零后重新积累不会被 0 “污染”成一串零。换一个角度理解零在这里相当于一个“硬切点”。任何跨过零的子数组乘积必然等于 0而 0 通常不会成为全局最大值除非全数组都是 0 或负数。DP 的“重新开始”选项nums[i]就是隐式地完成切分。边界条件的完整列表数组长度为 1ans初始化为nums[0]后直接不进入循环返回nums[0]天然正确数组里只有负数例如[-1, -2]正确结果是2fmin必须保留否则算成-1数组里有多个零例如[-1, 0, 2, 0]正确结果是2零负责切断2 自己单独成段最值在数组中间例如[1, 2, 3, 0, 4]答案是6而不是任何跨零的组合乘积可能溢出 int如果题目数据范围明确在 32 位整数内int没问题但某些变体可能要求long做中转写之前先看约束条件。最后提一句“连续子数组”这个限定。它要求子数组必须是连续的不能跳着选所以 DP 状态必须“以i结尾”。这也是为什么不能用“前 i 个元素的最大乘积”这种定义——那种定义无法知道最后一段从哪里开始递推时当前元素必须和前面最后一个元素接上才行。很多人做这题时会把“最大乘积子序列”和“最大乘积子数组”混在一起想只要把“以 i 结尾”这根弦绷住思路就不会跑偏。5. 一个反常规的解法正反双向扫描不用 DP 数组也能过除了 DP本题还有一个非常巧妙的解法正向扫描一遍反向扫描一遍同时维护累积乘积遇到 0 重置为 1。这个方法的正确性经常被拿来和 DP 对比它跑出来的答案是全局最大乘积。class Solution { public int maxProduct(int[] nums) { int max Integer.MIN_VALUE; int prefixProduct 1; for (int i 0; i nums.length; i) { prefixProduct * nums[i]; max Math.max(max, prefixProduct); if (prefixProduct 0) { prefixProduct 1; } } prefixProduct 1; for (int i nums.length - 1; i 0; i--) { prefixProduct * nums[i]; max Math.max(max, prefixProduct); if (prefixProduct 0) { prefixProduct 1; } } return max; } }原理是什么任何一个最大乘积子数组在原始数组里都对应一段连续区间。正向扫描时你只会“跑”到它左边到右边但如果你从左边算起中途可能被 0 打断甚至子数组中间没有 0 也可能因为“起点不对”而出现负数导致累积值不是最大值。反向扫描解决的是“起点在中间”的情况你不一定从第 0 个元素开始但你从右向左时等于把所有可能的“从某个位置向右”的前缀都算了一遍。一个直观的解释假设最大子数组在[l, r]之间正向扫描时l之前的负数可能让前缀乘积变成负的等到l后乘以正值的时候最终得到的不一定是最大。但反向扫描相当于从右侧逼近也会以r1之后的元素为后缀互相对冲两种情况覆盖了“该子数组左边剩奇数个负号”和“右边剩奇数个负号”这两类情况。只要子数组内部的总负号数为偶数总有一趟扫描能在两端恰好抵消。这个解法的复杂度同样是O(n)常数更小还省去了两个滚动变量。它的缺点是理解门槛略高面试时如果讲不清原理容易被追问“为什么反过来扫一遍就一定对”。所以我一般建议DP 是必会的标准解双向扫描可以作为加分项提及但不要在思路还没理清的时候硬上。在实践中这道题在 Java 中还有一个值得注意的细节Math.max里如果使用int直接乘prefixProduct可能溢出。LeetCode 原生数据范围通常不挖这个坑但你在本地测试任意大数组时最好留意。稳妥起见可以定义成long最后强转int不过严格来说要依据题目约束来判断。6. 从这题能顺带掌握的面试心法与扩展玩法这道题刷完不白刷它可以扩展出不少相关的变形题理解深了面试时还能借题发挥。第一个扩展方向二维数组的“最大乘积子矩阵”。把二维问题压缩成一维是常见套路固定上下边界后把每一列的元素乘起来变成一个一维数组再跑一维maxProduct即可。这个解法的时间复杂度是O(m^2 * n)其中m是行数笔试中属于比较合理的复杂度。第二个扩展方向乘积最小连续子数组。只需要把最终答案的初始化从max改成min其余转移公式原封不动即可。很多同学不知道实际上这道题的正解代码里本来就同时维护了最大和最小答案只是顺手取其中一个而已。第三个扩展方向不限制连续让你求“取任意个数字的最大乘积”。如果你理解了两个状态的原理就会发现非连续版本的贪心策略完全不同它要求按正数、负数、零分类讨论和本题的解法天然区分。面试官很喜欢用这两个问题对比看你能不能“分得清”。再聊一点面试心法。很多候选人拿到这道题都会直接开写 DP但我发现面试官真正关注的是以下三件事有没有主动解释“为什么只维护最大值是错的”——这比直接写对代码更能证明你理解了问题的本质写滚动变量时是否留意到更新顺序——这是最常见的 bug 源能不能在白板上画出状态转移的依赖关系——哪怕一两句话也好能说清楚i时刻只用i-1空间优化就不是“背模板”而是“自然推出来”。我当年第一次解这题时也是先写一个朴素O(n^2)的暴力解然后被一个极端数据卡超时才去研究这两状态 DP 的。如果你现在还停留在暴力枚举的阶段不必有压力这很正常。难点不在“写出来”而在“理解递推为什么是完备的”。最后分享一个调试小技巧如果你写完 DP 代码发现答案不对不要急着打断点先准备一个长度 3 的小数组比如[-1, -2, -3]手动按 DP 表格把fmax[i]和fmin[i]列出来再对比程序输出。大多数情况就是更新顺序写错了或者把nums[i]单独作为候选漏掉。这种小数据测试法比在 IDE 里刷日志快得多也更能帮你积累对动态规划的直觉。