题目描述给你一个整数数组nums请你找出数组中乘积最大的非空连续子数组该子数组中至少包含一个数字并返回该子数组所对应的乘积。子数组是数组中连续的非空元素序列。测试用例的答案是一个32-位整数。请注意一个只包含一个元素的数组的乘积是这个元素的值。示例 1:输入:nums [2,3,-2,4]输出:6解释:子数组 [2,3] 有最大乘积 6。示例 2:输入:nums [-2,0,-1]输出:0解释:结果不能为 2, 因为 [-2,-1] 不是子数组。解题思路方法一动态规划核心思路因为存在负数最小值乘以负数可能变成最大值。所以需要同时维护maxProd以当前元素结尾的最大乘积minProd以当前元素结尾的最小乘积状态转移对于每个nums[i]newMax max(nums[i], maxProd * nums[i], minProd * nums[i]) newMin min(nums[i], maxProd * nums[i], minProd * nums[i])为什么考虑nums[i]本身因为如果之前的乘积为 0 或负数不如从当前元素重新开始。具体过程示例nums [2,3,-2,4]inums[i]maxProdminProd说明0222初始化13632*36, 2*362-2-2-12max(-2, 6*-2-12, 3*-2-6) -2344-48max(4, -2*4-8, -12*4-48) 4最大乘积 6✅nums [-2,0,-1]inums[i]maxProdminProd说明0-2-2-2初始化1000max(0, -2*00, -2*00) 02-10-1max(-1, 0*-10, 0*-10) 0最大乘积 0✅代码实现class Solution { public: int maxProduct(vectorint nums) { int maxProd nums[0]; int minProd nums[0]; int result nums[0]; for (int i 1; i nums.size(); i) { int num nums[i]; // 先保存 maxProd因为下面要更新 int tempMax maxProd; maxProd max({num, maxProd * num, minProd * num}); minProd min({num, tempMax * num, minProd * num}); result max(result, maxProd); } return result; } };更简洁的写法class Solution { public: int maxProduct(vectorint nums) { int maxProd 1, minProd 1; int result INT_MIN; for (int num : nums) { if (num 0) swap(maxProd, minProd); maxProd max(num, maxProd * num); minProd min(num, minProd * num); result max(result, maxProd); } return result; } };交换技巧遇到负数时最大值和最小值互换因为负数会让大的变小、小的变大。复杂度分析维度复杂度说明时间复杂度O(n)一次遍历空间复杂度O(1)只用常数个变量关键细节1. 为什么需要同时维护最小值和最大值因为负数乘以负数会变成正数。nums [-2, 3, -4]-2 * 3 -6最小值-6 * -4 24最大值如果只维护最大值会错过这个情况。2. 为什么考虑nums[i]本身如果之前的乘积是 0 或负数不如从当前元素重新开始。nums [0, 2]0 * 2 0但从2重新开始乘积是23. 为什么用tempMax保存旧值因为更新maxProd后minProd的计算需要用到旧的maxProd。如果不保存maxProd已经被修改minProd会算错。4. 和「最大子数组和」的区别题目区别53. 最大子数组和加法只需维护最大值152. 乘积最大子数组乘法需要维护最大值和最小值总结要点说明核心思想同时维护最大乘积和最小乘积状态转移maxProd max(num, maxProd*num, minProd*num)关键技巧负数会让最大最小互换时间复杂度O(n)空间复杂度O(1) 
长河君 · 2026/10/10 21:06:24 · 阅读 1.2k 【动态规划-8】152.乘积最大子数组
题目描述给你一个整数数组nums请你找出数组中乘积最大的非空连续子数组该子数组中至少包含一个数字并返回该子数组所对应的乘积。子数组是数组中连续的非空元素序列。测试用例的答案是一个32-位整数。请注意一个只包含一个元素的数组的乘积是这个元素的值。示例 1:输入:nums [2,3,-2,4]输出:6解释:子数组 [2,3] 有最大乘积 6。示例 2:输入:nums [-2,0,-1]输出:0解释:结果不能为 2, 因为 [-2,-1] 不是子数组。解题思路方法一动态规划核心思路因为存在负数最小值乘以负数可能变成最大值。所以需要同时维护maxProd以当前元素结尾的最大乘积minProd以当前元素结尾的最小乘积状态转移对于每个nums[i]newMax max(nums[i], maxProd * nums[i], minProd * nums[i]) newMin min(nums[i], maxProd * nums[i], minProd * nums[i])为什么考虑nums[i]本身因为如果之前的乘积为 0 或负数不如从当前元素重新开始。具体过程示例nums [2,3,-2,4]inums[i]maxProdminProd说明0222初始化13632*36, 2*362-2-2-12max(-2, 6*-2-12, 3*-2-6) -2344-48max(4, -2*4-8, -12*4-48) 4最大乘积 6✅nums [-2,0,-1]inums[i]maxProdminProd说明0-2-2-2初始化1000max(0, -2*00, -2*00) 02-10-1max(-1, 0*-10, 0*-10) 0最大乘积 0✅代码实现class Solution { public: int maxProduct(vectorint nums) { int maxProd nums[0]; int minProd nums[0]; int result nums[0]; for (int i 1; i nums.size(); i) { int num nums[i]; // 先保存 maxProd因为下面要更新 int tempMax maxProd; maxProd max({num, maxProd * num, minProd * num}); minProd min({num, tempMax * num, minProd * num}); result max(result, maxProd); } return result; } };更简洁的写法class Solution { public: int maxProduct(vectorint nums) { int maxProd 1, minProd 1; int result INT_MIN; for (int num : nums) { if (num 0) swap(maxProd, minProd); maxProd max(num, maxProd * num); minProd min(num, minProd * num); result max(result, maxProd); } return result; } };交换技巧遇到负数时最大值和最小值互换因为负数会让大的变小、小的变大。复杂度分析维度复杂度说明时间复杂度O(n)一次遍历空间复杂度O(1)只用常数个变量关键细节1. 为什么需要同时维护最小值和最大值因为负数乘以负数会变成正数。nums [-2, 3, -4]-2 * 3 -6最小值-6 * -4 24最大值如果只维护最大值会错过这个情况。2. 为什么考虑nums[i]本身如果之前的乘积是 0 或负数不如从当前元素重新开始。nums [0, 2]0 * 2 0但从2重新开始乘积是23. 为什么用tempMax保存旧值因为更新maxProd后minProd的计算需要用到旧的maxProd。如果不保存maxProd已经被修改minProd会算错。4. 和「最大子数组和」的区别题目区别53. 最大子数组和加法只需维护最大值152. 乘积最大子数组乘法需要维护最大值和最小值总结要点说明核心思想同时维护最大乘积和最小乘积状态转移maxProd max(num, maxProd*num, minProd*num)关键技巧负数会让最大最小互换时间复杂度O(n)空间复杂度O(1)