题目描述
给你一个整数数组 nums ，请你找出数组中乘积最大的非空连续子数组，并返回该子数组所对应的乘积。
这道题和“最大子数组和”看起来有些像，但本质上要更难一些。因为求和的时候，状态变化比较单一，而求乘积时会受到负数和 0 的影响：
-
一个正数乘上负数，可能让最大值变成最小值；
-
-
遇到 0 时，前面的连续乘积会被直接断开。
所以这题不能只维护“当前位置结尾的最大乘积”，还必须同时维护“当前位置结尾的最小乘积”。
示例
示例 1
输入: nums = [2,3,-2,4]
输出: 6
解释: 子数组 [2,3] 的乘积最大，为 6。
示例 2
输入: nums = [-2,0,-1]
输出: 0
解释: 结果不能为 2，因为 [-2,-1] 不是连续子数组。
解题思路
一、为什么要同时维护最大值和最小值
如果这题只是求“当前位置结尾的最大乘积”，那么在遇到负数时就会出问题。
比如下面这个例子：
nums = [2, 3, -2, 4]
当遍历到 -2 时：
-
原来的最大乘积乘上
-2，会变成负数； -
原来的最小乘积乘上
-2，却有可能变成更大的正数。
再看一个更明显的例子：
nums = [-2, 3, -4]
遍历过程如下：
-
到
-2时，最大乘积是-2，最小乘积也是-2 -
到
3时，最大乘积是3，最小乘积是-6 -
到
-4时，原本的最小乘积-6乘上-4会变成24
也就是说：
最小值在某些时刻可以帮助我们得到最终的最大值。
因此我们需要维护两个状态：
-
imax：以当前位置结尾的最大乘积 -
imin：以当前位置结尾的最小乘积
二、状态转移
对于当前数字 nums[i]，有两种选择：
-
把它接到前面的连续子数组后面
-
从它自己重新开始
所以：
imax = Math.max(imax * nums[i], nums[i]);
imin = Math.min(imin * nums[i], nums[i]);
但是这里有一个关键点：
三、如果当前数字是负数，要先交换 imax 和 imin
因为负数会让大小关系翻转：
-
原本最大的乘积，乘上负数后可能变成最小的
-
原本最小的乘积，乘上负数后可能变成最大的
所以在更新之前，如果 nums[i] < 0，必须先交换：
if (nums[i] < 0) {
int tmp = imax;
imax = imin;
imin = tmp;
}
这一步是整道题最核心的地方。
代码实现
class Solution {
public int maxProduct(int[] nums) {
int max = Integer.MIN_VALUE, imax = 1, imin = 1;
for(int i=0; i<nums.length; i++){
if(nums[i] < 0){
int tmp = imax;
imax = imin;
imin = tmp;
}
imax = Math.max(imax * nums[i], nums[i]);
imin = Math.min(imin * nums[i], nums[i]);
max = Math.max(max, imax);
}
return max;
}
}
代码详解
1. 定义三个变量
int max = Integer.MIN_VALUE, imax = 1, imin = 1;
-
max：记录全局最大乘积 -
imax：记录当前位置结尾的最大乘积 -
imin：记录当前位置结尾的最小乘积
这里把 imax 和 imin 初始化为 1，是为了方便后续乘法计算。
2. 遍历整个数组
for(int i = 0; i < nums.length; i++)
对数组中的每个元素，更新当前位置结尾的最大值和最小值。
3. 遇到负数先交换
if(nums[i] < 0){
int tmp = imax;
imax = imin;
imin = tmp;
}
因为乘上负数后，最大值和最小值的角色会互换。
例如：
imax = 6, imin = -12, nums[i] = -2
那么：
-
imax * -2 = -12 -
imin * -2 = 24
此时原来的最小值反而能产生更大的结果。
4. 更新当前位置的最大最小乘积
imax = Math.max(imax * nums[i], nums[i]);
imin = Math.min(imin * nums[i], nums[i]);
这表示我们有两种选择：
-
接上前面的连续子数组
-
从当前元素重新开始
如果前面的乘积已经不合适了，那么就直接以当前元素作为新的起点。
5. 更新全局答案
max = Math.max(max, imax);
因为 imax 表示当前位置结尾的最大乘积，所以每次遍历完当前位置，都要更新一次全局最大值。
示例推演
我们以数组：
nums = [2, 3, -2, 4]
为例，模拟整个过程。
初始状态
max = -∞, imax = 1, imin = 1
遍历到 2
imax = max(1 * 2, 2) = 2
imin = min(1 * 2, 2) = 2
max = 2
遍历到 3
imax = max(2 * 3, 3) = 6
imin = min(2 * 3, 3) = 3
max = 6
遍历到 -2
先交换：
imax = 3, imin = 6
再更新：
imax = max(3 * -2, -2) = -2
imin = min(6 * -2, -2) = -12
max = 6
遍历到 4
imax = max(-2 * 4, 4) = 4
imin = min(-12 * 4, 4) = -48
max = 6
最终结果为：
6
再看一个更典型的例子
nums = [-2, 3, -4]
遍历到 -2
交换前: imax = 1, imin = 1
交换后: imax = 1, imin = 1
imax = max(1 * -2, -2) = -2
imin = min(1 * -2, -2) = -2
max = -2
遍历到 3
imax = max(-2 * 3, 3) = 3
imin = min(-2 * 3, 3) = -6
max = 3
遍历到 -4
先交换：
imax = -6, imin = 3
再更新：
imax = max(-6 * -4, -4) = 24
imin = min(3 * -4, -4) = -12
max = 24
最终答案是：
24
这个例子就很好地说明了：
维护最小乘积同样非常重要，因为它有可能在遇到负数时翻身变成最大乘积。
复杂度分析
时间复杂度
O(n)
只遍历了一次数组。
空间复杂度
O(1)
只使用了常数个变量。
和最大子数组和问题的区别
很多人会把这题和“最大子数组和”联系起来，但两者有一个重要区别：
-
最大子数组和只需要维护一个当前最优值
-
最大乘积子数组必须同时维护最大值和最小值
原因就在于乘积遇到负数时会发生符号翻转，而加法不会。
所以这题虽然也属于动态规划思想，但状态设计要更细一些。
总结
这道题的核心其实只有一句话：
由于负数会让最大值和最小值互换，所以必须同时维护当前位置结尾的最大乘积和最小乘积。
整体解题步骤如下：
-
用
imax记录当前位置结尾的最大乘积 -
用
imin记录当前位置结尾的最小乘积 -
遇到负数时先交换两者
-
更新当前位置的最大值和最小值
-
用
max维护全局答案
这是一道非常典型的动态规划题，难点不在代码长短，而在于状态设计是否想清楚。
如果能真正理解为什么要维护 imax 和 imin
