最大乘积动态规划陷阱：为何要同时维护最大值与最小值

东华大学OJ第39题“最大乘积”，做过的同学都知道，这题表面上是道动态规划入门题，实际上是个暗藏杀机的陷阱题。我第一次提交的时候，信誓旦旦觉得自己写对了，结果WA了好几次，最后才意识到这题跟常规的“最大子数组和”根本不是一个物种。今天我就把这题的来龙去脉、正解思路、代码实现和踩坑经验一次说清楚，给正在刷OJ的学弟学妹们做个参考。

在线编程与OJ评测系统普及之后，像东华大学OJ这样的平台成了无数计算机专业学生从入门到放弃的第一站。题目编号39，看起来平平无奇，但“最大乘积”这四个字背后，藏着动态规划里一个极其经典的思维转变：状态不仅要记录“最大值”，还得记录“最小值”。这题搞懂了，后面再遇到什么“乘积最大子数组”“最大子序列”之类的变种题，你都能一眼看穿出题人的小心思。

1. 题目到底在考什么：一个比“最大和”更阴险的兄弟题

1.1 在线编程与OJ评测系统里的经典题型

先说说这题所处的场景。OJ系统（Online Judge，在线评测系统）是计算机专业学生刷算法题的主要阵地，这类平台的特点是：提交代码后，系统自动用一组测试数据去跑你的程序，每个测试点都必须通过才能拿到AC。不能AC就等于白做，所以OJ刷题培养的不仅是“把题解出来”的能力，更是“把题在各种边界条件下写对”的能力。

东华大学OJ的39题“最大乘积”，题目描述很简短：给一个整数数组，找出乘积最大的连续子数组，返回这个最大乘积。这个“连续”二字是重点，但也是最容易被忽略的地方。它不是让你求整个数组所有元素相乘的结果，而是你必须从数组中截取一段连续区间，使得这一段区间内所有整数的乘积最大。

这类题目在各大OJ里都是常客，因为它在动态规划的教学链条里卡在一个很巧妙的位置。前面通常有“最大子数组和”（LeetCode 53），很多人做完那个题以后，会很自然地想：最大乘积不就是把加法换成乘法吗？然后兴致勃勃地写了个“只维护当前最大乘积”的版本，一提交，WA。恭喜踩坑。

1.2 加法思维和乘法思维的本质差异

先看一个最简单的例子：数组[-2, 3, -4]。这个数组的最大子数组和是多少？用“最大子数组和”的经典DP算法，答案是3——因为 -2 + 3 = 1，3 + (-4) = -1，都不如单独取3大。

但最大乘积是多少？答案是24，因为(-2) × 3 × (-4) = 24。注意，最后这个数字是从左到右全部乘起来才得到的。这就是加法和乘法的本质差异：加法里，负数只会让和变小，所以遇到负数直接“丢弃”就好；乘法里，负数乘以负数会变成正数，两个看起来很小的负数乘在一起，反而可能得到最大的正数。

换句话说，在计算最大乘积的过程中，你不仅要关心“当前乘积最大是多少”，还必须关心“当前乘积最小是多少”。因为当前这个最小值，如果下一步又碰到一个负数，它俩一乘，最小值就直接翻身变成最大值了。这就是整道题的核心思维转折点：动态规划状态里，必须同时维护最大值和最小值两个状态。

2. 思路拆解：从暴力到动态规划的“为什么”

2.1 暴力枚举为什么不可行

先看最朴素的做法：枚举所有可能的连续子数组，逐个计算乘积，取最大值。代码写起来倒是简单：

# 伪代码示意 max_val = -float('inf') for i in range(len(nums)): cur = 1 for j in range(i, len(nums)): cur *= nums[j] max_val = max(max_val, cur)

总共两层循环，时间复杂度是O(n²)。如果数组长度是10万，这就需要100亿次乘法运算，OJ的时限一般是1秒，稳稳的超时。就算你把内层循环优化一下，比如遇到0就提前break，最坏情况下依然是指数级的端点组合。

O(n²)的时间复杂度在大多数OJ题目里都是被判死刑的。所以必须把思路从“枚举所有子数组”切换到“利用已知信息递推”，这就是动态规划的切入角度。

2.2 两个状态，缺一不可

动态规划的核心是“用之前算过的结果，推出当前的结果”。对于最大子数组和问题，状态转移方程是：

dp[i] = max(nums[i], dp[i-1] + nums[i])

dp[i]表示以第i个元素结尾的子数组的最大和。它只有两种选择：从当前位置重新开始（nums[i]），或者跟前面的最大和拼接（dp[i-1] + nums[i]）。

如果把加法换成乘法，很多人会写：

# 这版是错的 dp[i] = max(nums[i], dp[i-1] * nums[i])

这个式子在数组为正数的场景下没问题，一旦出现负数就崩了。比如[-2, 3, -4]，按这个式子算：

• i=0：dp[0] = -2
• i=1：dp[1] = max(3, -2×3) = max(3, -6) = 3
• i=2：dp[2] = max(-4, 3×(-4)) = max(-4, -12) = -4

最终答案判成3，而正确答案是24。

问题出在哪？出在dp[1]只记录了“到位置1为止的最大乘积3”，但忽略了“到位置1为止的最小乘积-6”。当位置2的-4到来时，-6 × (-4) = 24才是正解，可你在状态里根本没保存这-6。

所以正解的状态必须是两个：

maxF[i]：以 nums[i] 结尾的子数组的最大乘积 minF[i]：以 nums[i] 结尾的子数组的最小乘积

每到一个新位置nums[i]，我们做三类比较：

• 重新开始：只取 nums[i]
• 和之前的maxF相乘：maxF[i-1] × nums[i]
• 和之前的minF相乘：minF[i-1] × nums[i]

maxF取这三者的最大值，minF取这三者的最小值。为什么minF也要参与？因为minF往往是负数，再乘以当前的负数，就可能变成最大的正数。

2.3 为什么必须暂存“上一个状态的旧值”

这里有个特别容易翻车的实现细节：在计算第i个位置时，maxF[i]和minF[i]都依赖于maxF[i-1]和minF[i-1]，也就是上一轮的“旧值”。如果你直接原地更新：

maxF = max(nums[i], maxF * nums[i], minF * nums[i]) minF = min(nums[i], maxF * nums[i], minF * nums[i]) # 这里maxF已经被更新了！

第二行里的maxF已经变成新值了，用它去算minF，就相当于在用当前轮的结果计算当前轮的结果，逻辑完全乱套。正确做法是先保存上一轮的旧值，或者用临时变量同时计算两个新值。

这个“暂存旧值”的细节，在实际编码中比理论推导更容易出错。我见过不少同学理论上懂，但一写代码就写错。后面第3章我会给出完整的正确写法，你可以直接对照着看。

3. 实操过程与核心环节实现

3.1 C++版本：从思路到可AC代码

这题最主流的写法是C++，因为东华大学OJ的很多算法课程就是用C/C++教学的。直接上代码：

class Solution { public: int maxProduct(vector<int>& nums) { // 以当前元素结尾的最大乘积和最小乘积 int maxF = nums[0]; int minF = nums[0]; int ans = nums[0]; for (int i = 1; i < nums.size(); i++) { // 先保存上一轮的值，防止覆盖导致逻辑错误 int mx = maxF; int mn = minF; maxF = max(nums[i], max(mx * nums[i], mn * nums[i])); minF = min(nums[i], min(mx * nums[i], mn * nums[i])); ans = max(ans, maxF); } return ans; } };

这段代码的关键点有三个，逐一说清楚。

第一，maxF和minF的初始值都设为nums[0]。有些同学习惯初始化为0或者INT_MAX，这在这里会出问题。如果初始化为0，而数组第一个元素是负数，maxF会错误地变成0；如果初始化为INT_MAX或INT_MIN，在做乘法的时候可能直接溢出。正确做法就是老老实实用第一个元素初始化。

第二，mx和mn这两个临时变量是灵魂。它们保存的是第i-1轮的状态，也就是旧值。在真正更新maxF和minF之前，这两玩意儿不能丢。举一个具体例子：nums = [2, -5, -3]。初始时maxF=2，minF=2。

• i=1时，cur=-5，mx=2，mn=2。maxF = max(-5, -10, -10) = -5，minF = min(-5, -10, -10) = -10。
• i=2时，cur=-3，mx=-5，mn=-10。maxF = max(-3, 15, 30) = 30，minF = min(-3, -15, -10) = -15。ans=30，正确。

如果不用临时变量，更新完maxF后再算minF，那么minF会用到刚刚更新过的maxF旧值，结果就会错。

第三，ans每轮都要更新为maxF的最大值。因为最大值不一定出现在数组末尾，可能出现在中间的某个位置。比如数组[1, 2, 3, 0, 0]，最大乘积6出现在下标2，遍历到后面的0时maxF变成了0，但正确答案仍是6。所以ans要始终记录历史最大值。

3.2 Python版本：同样的逻辑，更简洁的写法

Python版本逻辑完全一致，只是语法略有不同。如果你在OJ上用Python提交，可以直接用下面这段：

from typing import List class Solution: def maxProduct(self, nums: List[int]) -> int: max_f = nums[0] min_f = nums[0] ans = nums[0] for num in nums[1:]: # 保留旧值 mx, mn = max_f, min_f # 更新最大值：可能是当前元素本身、最大值乘当前元素、最小值乘当前元素 max_f = max(num, mx * num, mn * num) # 更新最小值：同理 min_f = min(num, mx * num, mn * num) ans = max(ans, max_f) return ans

这版代码和C++版本一一对应，没有任何多余的复杂处理。值得一提的是Python里max和min可以一次传入三个参数，写起来比C++的嵌套max简洁不少。

3.3 边界条件与测试用例

刷OJ只写代码不做边界测试等于白刷。我总结了几个必须验证的边界场景，直接做成表格给你对照：

尤其要注意全负数场景。比如[-1, -2, -3]，正确答案是6，也就是取前两个负数的乘积。很多同学以为全负数数组的答案就是最大的那个数，那是绝对错误的。有了minF这个状态，负数乘以负数就能算出正数。

4. 常见错误与排查技巧实录

4.1 只维护最大值：最典型的翻车现场

这是90%的人第一次提交会掉的坑。写法看起来逻辑自洽：

// 错误示范 int maxF = nums[0], ans = nums[0]; for (int i = 1; i < nums.size(); i++) { maxF = max(nums[i], maxF * nums[i]); ans = max(ans, maxF); }

用[-2, 3, -4]一测就露馅。因为maxF丢掉了负数状态-6，导致后续的-4无法翻身。这类错误在OJ上表现就是“部分测试点WA（错误答案）”，但案例太小又看不出来，非常难排查。我的排查建议是：WA的时候别急着看别人的题解，先用几个手工构造的负负得正用例测一遍自己的程序，80%的问题当场就能暴露。

4.2 初始值设置错误：把ans设成0

还有一种经典错误，是把ans初始化为0：

int ans = 0; // 错误示范

如果数组全是负数，比如[-3, -2, -1]，正确答案是6，但程序遍历过程中ans一开始就是0，永远大于任何负数乘积，最后输出0。这种错误的隐蔽性极高，因为你用正数数组测永远测不出来。记住一条铁律：涉及乘积类的极值问题，初始值要么设为第一个元素，要么设为INT_MIN，千万别默认设为0。

4.3 覆盖顺序问题：更新顺序错了，逻辑全乱

在第2章末尾我已经提过“暂存旧值”的问题，这里用一个更直观的版本再演示一下错误：

# 错误示范：max_f更新后，min_f的计算被污染 max_f = max(num, max_f * num, min_f * num) min_f = min(num, max_f * num, min_f * num) # 此时max_f是新的了

这种写法在nums = [2, -3, -4]上测试，会得到错误答案。为什么？因为第二个min_f计算时用到的max_f已经是本轮更新后的新值，它失去了和上一轮max_f的组合可能。用临时变量或者一行同时赋值都能解决这个问题，我个人的习惯是写临时变量，可读性更好。

4.4 除了动态规划，还有别的解法吗

刷题久了你会发现，同一个知识点可以有多种切入角度。这题除了DP，还有一个“按0分段”的数学思路：

把数组按0切开，每一段里没有0，那么乘积的绝对值会随着长度增加单调递增（不考虑符号时）。这时最大乘积只可能是三种情况：整段乘积、去掉这一段最左边负数后的乘积、去掉这一段最右边负数后的乘积。因为如果整段乘积是负数，去掉一个负数就能变正；如果整段乘积是正数，那整段就是答案；如果负数个数为偶数，整段必为正，直接取整段。这个思路不需要DP，只需要一次线性扫描加少量前缀乘积，也是O(n)时间，代码写起来甚至更短。

不过实际面试和考试中，DP版是被广泛认可的通用解，因为它不需要考虑各种分段细节，思维量更低，而且遇到0也能自动处理。我的建议是：考试写DP，稳；平时训练可以拿“按0分段”的思路来验证自己对负数规律的理解。

4.5 大数溢出问题的提醒

最后说一个很多人忽略的细节：int型的溢出。数组里的元素可以在[-1000, 1000]级别，如果数组很长且正数很多，中间过程的乘积很可能超过int的范围。这题的测试数据如果比较温和，int勉强够用；如果数据比较极限，建议直接用long long保存maxF和minF。C++里定义成long long maxF = nums[0]，基本上就能避开溢出问题。Python不涉及这个，因为Python的整数可以无限大。

我在实际测试中遇到过一组数据：[1000, 1000, 1000, 1000, 1000]，int版直接溢出为负数，导致答案错误。这个坑特别隐蔽，因为溢出结果看起来像是一个正常的负数，你的程序不会崩，但就是WA。所以只要乘积题，我第一反应就是开long long，这已经是肌肉记忆了。

5. 从这道题延伸出去：一个思路，解决一类题

这题做完之后，你会发现一个特别有意思的现象：动态规划的状态设计，不是拍脑袋想出来的，而是根据“当前选择会受到哪些历史因素的影响”来确定的。最大子数组和只受“历史最大值”影响，所以一个状态够用；最大乘积同时受“历史最大值”和“历史最小值”影响，所以必须两个状态。

把这种思维方式迁移出去，你就可以解决一系列“看起来差不多，但其实完全不一样”的题目。比如求最大绝对值的连续子数组、求乘积为正数的最长子数组长度、求加减交替的最长子序列……这些题的共性都是：状态转移时，你不仅要考虑“最优状态”，还要考虑“最劣状态”。因为最劣状态在某些条件下会翻转成最优状态。

我个人的学习心得是：做OJ题不能只看AC了没有，你得学会“给自己出题”。比如这题AC了，你可以改一改：“如果允许跳过而不是丢弃0，答案会怎样变化？”“如果数组长度达到10的6次方，空间复杂度能否从O(1)降到O(1)？要不要开数组？”这种头脑实验比盲目刷下一题有用得多。

最后分享一个小技巧，是我刷了上百道DP题之后总结出来的：遇到动态规划题，先别看题解，手工构造五个用例（正常用例、全正数、全负数、含0、单个元素），在每个用例上把转移过程手推一遍。推不出矛盾，说明你的状态设计合理；推到一半发现结果不对，恭喜你，你已经提前发现了隐藏的坑。这道“最大乘积”题，只要你能靠手推发现“必须同时维护最大值和最小值”，那你的DP基本功就真的过关了。