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

1. 问题引入为什么乘积最大子数组这么难第一次看到LeetCode 152题时我心想这不就是最大子数组和的变种吗结果被负数狠狠教育了。还记得当时用最大子数组和的思路写代码遇到[2,-3,-2,4]直接翻车——正确答案应该是48全数组乘积但我的代码却返回6前两个数乘积。关键矛盾点在于乘积具有符号敏感性。一个负数能让最大值瞬间变最小值也能让最小值逆袭成最大值。举个例子当前最大值是6遇到-26 × (-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]为例自立门户从当前数字重新开始nums[i]继承遗产maxDP[i-1] * nums[i]正数乘正数逆袭翻盘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 初始化与边界处理初始状态很简单当i0时子数组只能是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(vectorint nums) { if (nums.empty()) return 0; int res nums[0], n nums.size(); vectorint 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(vectorint 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我总结了几类必测场景用例类型示例输入预期输出检查目标全正数[2,3,4]24基础功能含单个负数[2,-3,4]4负数中断连续性负号反转[-2,3,-4]24最小值变最大值含零[2,0,3]3零值重置全负数[-2,-3,-1]6负负得正单元素[5]5边界条件特别建议测试[3,-1,4,-1,2]这个案例最优解是48全部相乘能检验算法是否考虑全局乘积。