152. 乘积最大子数组

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

示例 1:

输入: [2,3,-2,4]
输出: 6
解释: 子数组 [2,3] 有最大乘积 6。
示例 2:

输入: [-2,0,-1]
输出: 0
解释: 结果不能为 2, 因为 [-2,-1] 不是子数组。

在做本题之前如果做过最大子数组的和，那会更加有联想的想法。
看到本题其实第一想法就是动态规划，其实本题由于是连续子数组，确实可以用动归来做，因为后面的解依赖于前面的解，这和求最大子数组的和是一样的。
但是乘法，需要注意数组里出现负数 或者 0的时候特殊处理。
我们一开始初始化一个 imax ，imin 都是1，我们把他们当做数组中当前的最大乘积和最小乘积，为什么要记录一个最小乘积？原因就在于，当我们遇见负数的时候，最小乘积乘以负数就会比最大乘积要大了。

当我们遇见一个负数的时候，我们先将数组中的最大乘积和最小乘积进行交换。由于我们将其初始化都为1，因此即便是第一个数是负数进行交换也是可以的。
然后我们进行判断，当前数字乘imax 是否大于 当前数字， 如果不大于最大数字，那么我们直接取当前数字为最大乘积值，否则就取两数乘积为最大乘积值。原因就在于我们要求的是连续子数组，因此当我们遇见当前数字乘imax小于当前数字，那我们就需要重新设定imax的头了，换言之就是重新从当前数字来计算乘积最大数组。
我们对imin也是同样的处理。
我们还需要一个值来存储最大值，原因就在于有时候从一个新头开始求最大值或者最小值，就会丢弃掉之前的imax或者imin，我们不能确保之后值一定比当前的值大，同时当数组中出现0的时候就更加需要一个数来存储最大数，每次迭代进行判断当imax>max就替换max。

代码如下：

class Solution {
    public int maxProduct(int[] nums) {
        
        int max = Integer.MIN_VALUE;
        int imax = 1, imin = 1;
        for (int i = 0; i < nums.length; i++){
            if (nums[i] < 0){
                int temp = imax;
                imax = imin;
                imin = temp;
            }
            imax = imax * nums[i] > nums[i] ? imax * nums[i] : nums[i];
            imin = imin * nums[i] < nums[i] ? imin * nums[i] : nums[i];
            max = max > imax ? max : imax;
        }
        return max;
    }
}

来源：力扣（LeetCode）
链接：https://leetcode-cn.com/problems/maximum-product-subarray
著作权归领扣网络所有。商业转载请联系官方授权，非商业转载请注明出处。