【Hot 100 刷题计划】 LeetCode 152. 乘积最大子数组 | C++ 动态规划 (绝妙 swap 翻转技巧)

张开发
• 2026/4/16 21:16:31 • 15 分钟阅读

最新文章

推荐文章

相关文章

分享文章

【Hot 100 刷题计划】 LeetCode 152. 乘积最大子数组 | C++ 动态规划 (绝妙 swap 翻转技巧)
LeetCode 152. 乘积最大子数组 题目描述题目级别中等给你一个整数数组nums请你找出数组中乘积最大的非空连续子数组该子数组中至少包含一个数字并返回该子数组所对应的乘积。测试用例的答案是一个32-位整数。示例 1:输入:nums [2,3,-2,4]输出:6解释: 子数组[2,3]有最大乘积6。示例 2:输入:nums [-2,0,-1]输出:0解释: 结果不能为 2, 因为[-2,-1]不是子数组不连续。 破题思路动态规划的“负负得正”陷阱这道题和“最大子数组和”非常像但乘法有一个致命的特殊性负号的存在。一个极其小的负数如果再乘上一个负数会瞬间翻盘变成一个巨大的正数因此我们不能只记录“当前的最大乘积”我们还必须同时记录“当前的最小乘积”因为它有潜力在遇到下一个负数时变身成最大乘积。本解法的极客高光点 (Swap 魔法)常规思路是在每次遍历时同时用nums[i]、nums[i] * max_dp、nums[i] * min_dp三个数去求新的最大值和最小值代码写起来非常繁琐。但我们回归数学本质当遇到一个负数时乘积的大小关系会发生反转。所以如果我们发现当前数字nums[i] 0我们直接把维护的“当前最大值mam”和“当前最小值mim”互换位置 (swap)互换之后我们就可以像处理正数一样毫无顾忌地直接更新mam和mim了。这个思路极其优雅堪称神来之笔。 C 代码实现 (O(1) 空间极简版)classSolution{public:intmaxProduct(vectorintnums){// mim 维护以当前元素结尾的最小乘积// mam 维护以当前元素结尾的最大乘积intmim1,mam1;intresINT_MIN;// 全局最大结果for(inti0;inums.size();i){// 绝妙逻辑遇到负数乘积的极值属性反转直接 swapif(nums[i]0){swap(mim,mam);}// 要么是从前面连乘过来的要么就是从当前元素重新开始自己单干mimmin(nums[i],mim*nums[i]);mammax(nums[i],mam*nums[i]);// 每次更新全局最大值resmax(res,mam);}returnres;}};

更多文章