乘积最大子数组
Maximum Product Subarray
在整数数组中找一个连续子数组，使它的乘积最大，返回这个乘积。
在力扣中练习题目描述
给你一个整数数组 nums ，请你找出数组中乘积最大的非空连续 子数组（该子数组中至少包含一个数字），并返回该子数组所对应的乘积。
测试用例的答案是一个 32-位 整数。
请注意，一个只包含一个元素的数组的乘积是这个元素的值。
示例 1:
输入: nums = [2,3,-2,4]
输出: 6
解释: 子数组 [2,3] 有最大乘积 6。
示例 2:
输入: nums = [-2,0,-1] 输出: 0 解释: 结果不能为 2, 因为 [-2,-1] 不是子数组。
提示:
1 <= nums.length <= 2 * 104-10 <= nums[i] <= 10nums的任何子数组的乘积都 保证 是一个 32-位 整数
解题思路
主解法
双状态 DP · 同时记最大和最小
负号会把最大变最小，所以两条状态都要留
如果数组全是正数，只需记“以 i 结尾的最大乘积”。但负数会让大小关系翻转：当前最大的乘积乘上负数，可能变成最小的；当前最小的乘积乘上负数，反而可能变成最大的。
所以同时维护两个状态：
最大[i] = max(nums[i], 最大[i-1] × nums[i], 最小[i-1] × nums[i])
最小[i] = min(nums[i], 最大[i-1] × nums[i], 最小[i-1] × nums[i])
自拟主例 nums = [3,2,-1,4]。前两项得到最大 6、最小 2；乘上 -1 后，6 变成 -6、2 变成 -2，新的最大值反而是 -1（只取当前元素）。最后一项 4 让最大回到 4，但全局最优仍是 6。
分步图解
nums[1] = 2：三个候选 2、3×2、3×2；最大 6，最小 2。
- max[i]
- 6
- min[i]
- 2
- best
- 6
乘积最大子数组 · 最大 / 最小双状态
最大[i] / 最小[i]：以 nums[i] 结尾的连续子数组的最大 / 最小乘积；答案是所有最大[i] 的最大值
最大乘积6最小乘积2全局最优6
最大[1]=max(nums[1], 最大[0] × nums[1], 最小[0] × nums[1])=
max(2, 3 × 2, 3 × 2)=6最小[1]=min(nums[1], 最大[0] × nums[1], 最小[0] × nums[1])=2候选计算值结果
nums[1]
22最小最大[0]
3 × 26最大最小[0]
3 × 26最大未计算
每轮都要把“自己单独开头”作为一个候选，否则遇到负数会接不上。全局答案 best 独立记录，因为最大子数组不一定在末尾结束。
图解
乘积最大子数组 · 最大 / 最小双状态
最大[i] / 最小[i]：以 nums[i] 结尾的连续子数组的最大 / 最小乘积；答案是所有最大[i] 的最大值
最大乘积4最小乘积-24全局最优6
最大[3]=max(nums[3], 最大[2] × nums[3], 最小[2] × nums[3])=
max(4, -1 × 4, -6 × 4)=4最小[3]=min(nums[3], 最大[2] × nums[3], 最小[2] × nums[3])=-24候选计算值结果
nums[3]
44最大最大[2]
-1 × 4-4—最小[2]
-6 × 4-24最小时间 O(n)，只用了常数个变量，空间 O(1)。
时间 O(n)空间 O(1)
易错点
- 只维护最大乘积：乘上负数后最大值会来自原来的最小值，直接漏解。
- 忘记把 nums[i] 本身作为候选：前面乘积为 0 或负数时，单独开头才是最优。
- 返回 high（最后一项结尾的最大值）：答案可能在数组中间，必须用 best 记录全局最大。
代码与演示
演示输入
nums = [3,2,-1,4]第一个数自己就是最大值和最小值：最大[0] = 最小[0] = 3。
- max[0]
- 3
- min[0]
- 3
乘积最大子数组 · 最大 / 最小双状态
最大[i] / 最小[i]：以 nums[i] 结尾的连续子数组的最大 / 最小乘积；答案是所有最大[i] 的最大值
最大乘积—最小乘积—全局最优3
初值
最大[0] = 最小[0] = nums[0]候选计算值结果
初值：单个元素的乘积就是它自己
未计算
查看 C++ 代码
延伸阅读
- “以 i 结尾”的状态定义适合连续子数组；和最长递增子序列不同，这里不能跳过元素。
- 如果要求输出子数组本身，需要额外记录起点和终点；只维护乘积无法还原区间。