LeetCode 152. 乘积最大子数组：从双状态DP到空间优化【C++/Java精讲】

1. 问题引入：为什么乘积最大子数组这么难？

第一次看到LeetCode 152题时，我心想："这不就是最大子数组和的变种吗？"结果被负数狠狠教育了。还记得当时用最大子数组和的思路写代码，遇到[2,-3,-2,4]直接翻车——正确答案应该是48（全数组乘积），但我的代码却返回6（前两个数乘积）。

关键矛盾点在于：乘积具有符号敏感性。一个负数能让最大值瞬间变最小值，也能让最小值逆袭成最大值。举个例子：

• 当前最大值是6，遇到-2：6 × (-2) = -12（变成最小值）
• 当前最小值是-3，遇到-2：-3 × (-2) = 6（反而成了最大值）

这就像坐过山车，必须同时记录最高点和最低点，才能应对突然的下坠或上升。这也是为什么简单的单状态DP会失效，必须引入双状态动态规划。

2. 双状态DP的核心思想

2.1 状态定义的艺术

传统DP通常用f[i]表示以nums[i]结尾的子数组最优解，但在这里我们需要两个数组：

• maxDP[i]：以nums[i]结尾的子数组最大乘积
• minDP[i]：以nums[i]结尾的子数组最小乘积

为什么需要最小值？看这个例子：

nums = [3, -2, -4]

当处理到-4时：

• 前一步的最大值是3 × (-2) = -6
• 前一步的最小值就是-2本身
• -6 × (-4) = 24（新的最大值来自最小值×负数）

2.2 状态转移方程推导

状态转移需要考虑三种情况（以maxDP[i]为例）：

1. 自立门户：从当前数字重新开始（nums[i]）
2. 继承遗产：maxDP[i-1] * nums[i]（正数乘正数）
3. 逆袭翻盘：minDP[i-1] * nums[i]（负数乘负数）

用数学表达式就是：

maxDP[i] = \max(nums[i],\ maxDP[i-1]×nums[i],\ minDP[i-1]×nums[i]) minDP[i] = \min(nums[i],\ minDP[i-1]×nums[i],\ maxDP[i-1]×nums[i])

2.3 初始化与边界处理

初始状态很简单：

• 当i=0时，子数组只能是nums[0]本身：

maxDP[0] = minDP[0] = nums[0];

但要注意数组越界问题。有次我写Java代码时没检查空数组，直接nums[0]导致崩溃。完整初始化应该：

if (nums.length == 0) return 0; int res = nums[0];

3. C++与Java实现对比

3.1 C++实现细节

class Solution { public: int maxProduct(vector<int>& nums) { if (nums.empty()) return 0; int res = nums[0], n = nums.size(); vector<int> maxDP(n), minDP(n); maxDP[0] = minDP[0] = nums[0]; for (int i = 1; i < n; ++i) { maxDP[i] = max(nums[i], max(maxDP[i-1]*nums[i], minDP[i-1]*nums[i])); minDP[i] = min(nums[i], min(minDP[i-1]*nums[i], maxDP[i-1]*nums[i])); res = max(res, maxDP[i]); } return res; } };

性能特点：

• vector的连续内存访问效率高
• 注意max的三重嵌套调用，可以拆分成两步更清晰

3.2 Java实现注意点

class Solution { public int maxProduct(int[] nums) { if (nums.length == 0) return 0; int res = nums[0]; int[] maxDP = new int[nums.length]; int[] minDP = new int[nums.length]; maxDP[0] = minDP[0] = nums[0]; for (int i = 1; i < nums.length; i++) { maxDP[i] = Math.max(nums[i], Math.max(maxDP[i-1]*nums[i], minDP[i-1]*nums[i])); minDP[i] = Math.min(nums[i], Math.min(minDP[i-1]*nums[i], maxDP[i-1]*nums[i])); res = Math.max(res, maxDP[i]); } return res; } }

易错点：

• Java数组初始化自动填0，但我们的逻辑不需要这个特性
• Math.max只支持两个参数，需要嵌套调用

4. 空间优化：从O(n)到O(1)

4.1 为什么可以优化？

观察状态转移方程发现：maxDP[i]和minDP[i]只依赖于前一个状态。就像斐波那契数列，我们不需要保存整个数组，只需维护滚动变量。

4.2 优化后的C++实现

int maxProduct(vector<int>& nums) { if (nums.empty()) return 0; int res = nums[0], maxP = nums[0], minP = nums[0]; for (int i = 1; i < nums.size(); ++i) { int currMax = max(nums[i], max(maxP*nums[i], minP*nums[i])); int currMin = min(nums[i], min(minP*nums[i], maxP*nums[i])); res = max(res, currMax); maxP = currMax; // 注意要先更新res再覆盖变量！ minP = currMin; } return res; }

关键技巧：

• 使用currMax和currMin作为临时变量
• 更新顺序很重要：先计算→更新res→最后覆盖旧值

4.3 Java优化版

public int maxProduct(int[] nums) { if (nums.length == 0) return 0; int res = nums[0], maxP = nums[0], minP = nums[0]; for (int i = 1; i < nums.length; i++) { int preMax = maxP; // 必须保存旧值！ maxP = Math.max(nums[i], Math.max(maxP*nums[i], minP*nums[i])); minP = Math.min(nums[i], Math.min(minP*nums[i], preMax*nums[i])); res = Math.max(res, maxP); } return res; }

踩坑记录：

• 直接使用maxP计算minP会导致值被覆盖，必须先用preMax保存旧值
• 实测下来空间消耗从40MB降到38MB，虽然不多但算法更优雅

5. 测试用例设计技巧

好的测试用例能帮你发现90%的bug，我总结了几类必测场景：

特别建议测试[3,-1,4,-1,2]这个案例，最优解是48（全部相乘），能检验算法是否考虑全局乘积。