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

题目描述给你一个整数数组nums请你找出数组中乘积最大的非空连续子数组该子数组中至少包含一个数字并返回该子数组所对应的乘积。测试用例的答案是一个32 位整数。注意一个只包含一个元素的数组的乘积就是这个元素的值。示例输入nums [2,3,-2,4]→ 输出6子数组[2,3]有最大乘积 6输入nums [-2,0,-1]→ 输出0结果不能为 2因为[-2,-1]不是子数组解题思路总览方法思路时间复杂度空间复杂度动态规划同时维护最大乘积和最小乘积因为负数会使最小变最大O(n)O(1)分治递归处理每个区间考虑奇数个负数和偶数个负数的情况O(n log n)O(log n)暴力枚举枚举所有子数组计算乘积O(n^2)O(1)本题采用动态规划方法。完整代码classSolution{public:intmaxProduct(vectorintnums){intansINT_MIN,imax1,imin1;for(inti0;inums.size();i){if(nums[i]0){inttempimax;imaximin;imintemp;}imaxmax(imax*nums[i],nums[i]);iminmin(imin*nums[i],nums[i]);ansmax(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逐行解析intansINT_MIN,imax1,imin1;含义ans记录全局最大乘积初始化为最小整数imax记录以当前位置结尾的连续子数组的最大乘积imin记录以当前位置结尾的连续子数组的最小乘积初始化为 1 是因为乘积的起始值为 1单位元for(inti0;inums.size();i)含义遍历数组依次计算以每个位置结尾的子数组的最大乘积。if(nums[i]0){inttempimax;imaximin;imintemp;}含义如果当前元素是负数会将最大乘积和最小乘积互换。因为负数乘以最大数会变成最小数乘以最小数会变成最大数。imaxmax(imax*nums[i],nums[i]);含义更新imax。取「之前累积的最大乘积乘以当前元素」和「重新从当前元素开始」中的较大值。iminmin(imin*nums[i],nums[i]);含义更新imin。取「之前累积的最小乘积乘以当前元素」和「重新从当前元素开始」中的较小值。ansmax(ans,imax);含义更新全局最大乘积。returnans;含义返回所有子数组中的最大乘积。核心思想为什么需要同时维护最大和最小乘积因为数组中可能存在负数。以[2, 3, -2, 4]为例当遍历到-2时之前累积的最大乘积是6如果继续乘以负数-26 × (-2) -12变成很小的数但如果我们之前累积的是最小乘积呢2 × 3 × (-2) -12再乘以-2就变成24了所以当遇到负数时最大和最小会互换角色。必须同时记录最大和最小才能应对各种情况。复杂度分析复杂度值说明时间复杂度O(n)只需遍历一次数组空间复杂度O(1)只使用了常数个变量面试追问 FAQ问题答案为什么初始化imax imin 11 是乘法的单位元方便统一处理「从当前位置重新开始」的情况为什么不比较imax * nums[i]和1 * nums[i]因为nums[i]本身就是imax 1时imax * nums[i]的一种情况遇到 0 会怎样0 会让乘积变成 0同时是子数组的分界线。max(0, imax*0) 0会重新从下一个位置开始计算和最大子数组和53题有什么区别最大子数组和问题可以用贪心但乘积问题因为负数的存在必须用动态规划同时维护最大和最小如何输出具体的子数组额外记录每个位置的imax是来自之前的累积还是重新开始最后回溯得到起止位置进阶如何求乘积最小子数组将ans max(ans, imax)改为ans min(ans, imin)即可相关题目题号题目难度核心思路152乘积最大子数组中等动态规划最大/最小乘积53最大子数组和中等动态规划/贪心918环形子数组的最大和中等动态规划 环形数组1567乘积为正的最长子数组长度中等动态规划记录正/负乘积长度总结要点内容核心思想同时维护最大乘积和最小乘积因为负数会使两者互换状态定义imax[i] 以第 i 个元素结尾的连续子数组的最大乘积状态定义imin[i] 以第 i 个元素结尾的连续子数组的最小乘积状态转移遇到负数时交换 imax 和 imin然后imax max(imax*nums[i], nums[i])初始化imax imin 1ans INT_MIN结果返回遍历过程中的最大 ans