【力扣100题】48.乘积最大子数组

题目描述

给你一个整数数组nums，请你找出数组中乘积最大的非空连续子数组（该子数组中至少包含一个数字），并返回该子数组所对应的乘积。

测试用例的答案是一个32 位整数。注意，一个只包含一个元素的数组的乘积就是这个元素的值。

示例：

• 输入：nums = [2,3,-2,4]→ 输出：6（子数组[2,3]有最大乘积 6）
• 输入：nums = [-2,0,-1]→ 输出：0（结果不能为 2，因为[-2,-1]不是子数组）

解题思路总览

本题采用动态规划方法。

完整代码

classSolution{public:intmaxProduct(vector<int>&nums){intans=INT_MIN,imax=1,imin=1;for(inti=0;i<nums.size();i++){if(nums[i]<0){inttemp=imax;imax=imin;imin=temp;}imax=max(imax*nums[i],nums[i]);imin=min(imin*nums[i],nums[i]);ans=max(ans,imax);}returnans;}};

算法流程图

输入: nums = [2, 3, -2, 4] 初始化: ans = INT_MIN = -∞ imax = 1 imin = 1 i = 0, nums[0] = 2: 2 < 0? 否，不需要交换 imax = max(1*2, 2) = max(2, 2) = 2 imin = min(1*2, 2) = min(2, 2) = 2 ans = max(-∞, 2) = 2 i = 1, nums[1] = 3: 3 < 0? 否，不需要交换 imax = max(2*3, 3) = max(6, 3) = 6 imin = min(2*3, 3) = min(6, 3) = 3 ans = max(2, 6) = 6 i = 2, nums[2] = -2: -2 < 0? 是，交换 imax 和 imin temp = imax = 6 imax = imin = 3 imin = temp = 6 imax = max(3*(-2), -2) = max(-6, -2) = -2 imin = min(6*(-2), -2) = min(-12, -2) = -12 ans = max(6, -2) = 6 i = 3, nums[3] = 4: 4 < 0? 否，不需要交换 imax = max(-2*4, 4) = max(-8, 4) = 4 imin = min(-12*4, 4) = min(-48, 4) = -48 ans = max(6, 4) = 6 最终 ans = 6 输出: 6

逐行解析

intans=INT_MIN,imax=1,imin=1;

含义：

• ans记录全局最大乘积，初始化为最小整数
• imax记录以当前位置结尾的连续子数组的最大乘积
• imin记录以当前位置结尾的连续子数组的最小乘积
• 初始化为 1 是因为乘积的起始值为 1（单位元）

for(inti=0;i<nums.size();i++)

含义：遍历数组，依次计算以每个位置结尾的子数组的最大乘积。

if(nums[i]<0){inttemp=imax;imax=imin;imin=temp;}

含义：如果当前元素是负数，会将最大乘积和最小乘积互换。因为负数乘以最大数会变成最小数，乘以最小数会变成最大数。

imax=max(imax*nums[i],nums[i]);

含义：更新imax。取「之前累积的最大乘积乘以当前元素」和「重新从当前元素开始」中的较大值。

imin=min(imin*nums[i],nums[i]);

含义：更新imin。取「之前累积的最小乘积乘以当前元素」和「重新从当前元素开始」中的较小值。

ans=max(ans,imax);

含义：更新全局最大乘积。

returnans;

含义：返回所有子数组中的最大乘积。

核心思想：为什么需要同时维护最大和最小乘积？

因为数组中可能存在负数。

以[2, 3, -2, 4]为例：

• 当遍历到-2时，之前累积的最大乘积是6
• 如果继续乘以负数-2，6 × (-2) = -12，变成很小的数
• 但如果我们之前累积的是最小乘积呢？2 × 3 × (-2) = -12，再乘以-2就变成24了！

所以，当遇到负数时，最大和最小会互换角色。必须同时记录最大和最小，才能应对各种情况。

复杂度分析

面试追问 FAQ

相关题目

总结