题目

核心思路

这道题是一道很典型DP问题，直接穷举所有可能的子数组会发现有很多重复计算的部分，同时子数组的最大乘积是有最优的子结构的，因此可以考虑到使用DP方法来解决。
在乘法中有两种比较特殊的值 负数和0，遇到0会使得总的乘积直接变成0，而遇到负数会使得最大值直接变成最小值，因此我们需要用两个数组来保存遍历到i位置的最大值imax[i]和最小值imin[i]，然后对负数分类讨论就可以解决负数的问题了。
然后来看0这个特殊元素，由于题目中提到子数组可以是单个元素，那么遇到任意一个元素，都要同时将之前乘积与本元素做比较来存入imax和imin，这样在遇到0的时候，要么取前边的乘积乘以0、要么直接取本元素0，直接将这种可能包括其中了，即：

            if(nums[i - 1] < 0){
                imax[i] = Math.max(imin[i - 1] * nums[i - 1], nums[i - 1]);
                imin[i] = Math.min(imax[i - 1] * nums[i - 1], nums[i - 1]);
            }else{
                imax[i] = Math.max(imax[i - 1] * nums[i - 1], nums[i - 1]);
                imin[i] = Math.min(imin[i - 1] * nums[i - 1], nums[i - 1]);
            }

这样得到的每个imax[i]都是可能的最大值，所以每次循环取一次最大值：

max = Math.max(max, imax[i]);

接下来就是分析递推公式，优化空间复杂度了。容易发现，imax和imin都只与他们的上一个值相关，因此，可以将空间优化为O(1)，仅使用两个变量来表示这两个值，即：

            if(nums[i - 1] < 0){
                imax = Math.max(imin * nums[i - 1], nums[i - 1]);
                imin = Math.min(imax * nums[i - 1], nums[i - 1]);
            }else{
                imax = Math.max(imax * nums[i - 1], nums[i - 1]);
                imin = Math.min(imin * nums[i - 1], nums[i - 1]);
            }

代码看起来还是很繁琐，上下的 if和else 部分只是换了imax和imin，表达式其他的地方一模一样，那么我们可以在遇到负数的时候交换imax和imin，然后去做计算，也就能让代码看着简洁一些。

完整代码

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

            imax = Math.max(imax * nums[i], nums[i]);
            imin = Math.min(imin * nums[i], nums[i]);
            max = Math.max(max, imax);
        }
        return max;
    }
}

找递推公式还是很需要锻炼的，自己还是差的很多啊。另笔者也是在学习中，如果有写的不对的地方还请指出，感恩相遇~