152.乘积最大子数组

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

测试用例的答案是一个 32-位 整数。

子数组 是数组的连续子序列。

思路

基本思想

为了得到连续的子数组乘积，说明当前子数组中的元素不能删除或者移动，只能在原数组的基础上求得结果，简单的来看，当前位置得到的最大连续子数组乘积与之前的位置有关，得到一个更新数组： $$ dp[i]=max(dp[i],dp[i-1]*nums[i]) $$ 当前位置的元素是否加入当前连续的子数组乘积中，取决于加入之后乘积能否变大，不能变大的原因是因为当前元素为负，但是这种思路只能解决部分问题，例如当nums数组为[2,3,-2,4]这种类型可以，但是一旦遇到[-3,-1,-1]这种数组，最终求出来的结果就会是-1，但是真正的结果为3

出现上面情况的原因是因为上面给出的更新公式只考虑了前面元素为正的情况，为负的情况直接丢弃了，但是一旦当前元素为负，前面又出现一个为负的连续子数组乘积，那么此时负负得正，就会得到一个最大的值，所以需要分情况讨论：

1. 当当前元素为正时，当前元素与之前的连续子数组的最大值相乘能得到一个更大的值
2. 当当前元素为负时，当前元素与之前的连续子数组的最小值相乘能得到一个更大的值

所以从当前位置向前看，不仅需要当前位置向前的最大连续子数组的乘积，还需要当前位置向前的最小连续子数组的乘积

有了上面的分析过程，当前元素所处位置的最大连续子数组的乘积的更新公式就变成了： $$ dpMax[i]=max(dpMax[i],dpMax[i-1]*nums[i],dpMin[i-1]*nums[i]) $$ 一共有三项，从中取出最大的一项，取出第一项的原因是因为前面是负数，当前元素是正数，例如[-3,1]中元素1所处的位置，或者当前元素为负数，前面是正数 ，例如[2,3,-1]中元素-1所处的位置

取出第二项的原因是因为当前元素为正，前面的元素也为正，例如[2,3,4]中元素4所处的位置

取出第三项的原因是因为当前元素为负，前面的元素也为负，例如[-3,-1,2]中元素-1所处的位置

另外需要注意的是，还需要维护一个dpMin来记录当前元素之前的最小连续子数组的乘积

$$ dpMin[i]=min(dpMin[i],dpMax[i-1]*nums[i],dpMin[i-1]*nums[i]) $$

相当于在原来的基础上维护了一个dpMin，解决了[-3,-1,-1]计算出的错误结果为-1的情况，使得最终的结果负负得正，计算出正确结果3

执行流程

1. 初始化dpMax和dpMin等于给定的nums数组中的值，因为最小的连续子数组的和就是只有当前元素
2. 结果暂时未第一个元素，由于要计算dpMax[i-1]或者dpMin[i-1]，所以i的下标从1开始，也就是从第二个元素开始统计
3. 按照更新公式更新dpMax和dpMin
4. 更新这两个数组的过程中，尝试找到最大的乘积作为最终的结果
5. 返回最终的结果

代码

根据以上分析，得出以下代码：

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
19
20
21

class Solution {
    public int maxProduct(int[] nums) {
        //由于算的是乘积,所以乘积的最小值也是当前元素本身
        //深拷贝不能浅拷贝
        int[] dpMax = Arrays.copyOf(nums,nums.length);
        int[] dpMin = Arrays.copyOf(nums,nums.length);
        int res=nums[0];
        for(int i=1;i<nums.length;++i){//遍历物品
            //由于当前元素可能是正数,也可能是负数,所以当前位置的最大乘积有三种情况

            dpMax[i]=Math.max(dpMax[i],
            Math.max(dpMin[i-1]*nums[i],dpMax[i-1]*nums[i]));
            
            //这个数组就是一个辅助数组
            dpMin[i]=Math.min(dpMin[i],
            Math.min(dpMin[i-1]*nums[i],dpMax[i-1]*nums[i]));              
            res=Math.max(dpMax[i],res);
        }
        return res;
    }
}

总结

主要是在正常的基础上要考虑负负得正也可能得到最大值的情况，然后增加了一个dpMin来记录当前位置向前的最小值，防止当前元素是一个负数无法统计到的情况，并且dpMax和dpMin在初始化时需要注意不能浅拷贝，需要深拷贝，所以不能使用

1
2

int[] dpMax = nums;
int[] dpMin = nums;

而是要使用

1
2

int[] dpMax = Arrays.copyOf(nums,nums.length);
int[] dpMin = Arrays.copyOf(nums,nums.length);