152. 乘积最大子数组：需要维护两个dp数组的动态规划问题.md

题目简述：

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

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

题目链接：152. 乘积最大子数组

动态规划思路

这个问题很显然是一个动态规划问题，但有趣的是相比于更平凡、更基础的只维护一个 $dp$ 数组的动态规划问题，我们需要维护两个 $dp$ 数组。

假设我们只设 $dp[i]$ 表示以 $\text{nums}[i]$ 结尾的最大非空连续子数组乘积，则 $$ dp[i]=\left{\begin{align} &\max\big{\text{nums}[i],\ \ \text{nums}[i]\times dp[i-1]\big},&&\text{nums}[i]\geqslant0\\ &,???,&&\text{nums}[i]<0 \end{align}\right. $$ 可以发现，我们无法处理 $\text{nums}[i]$ 为负的情况。

要解决这个问题也很简单，同时维护一个表示 $\text{nums}[i]$ 结尾的小非空连续子数组乘积的 $dp$ 数组就可以了，因为负号会改变数组的大小，原本较大的实数取负后将变得较小，原本较小的实数取负后将变得较大，因此有 $$ \mathrm{maximum}[i]=\max\big{\text{nums}[i],\ \ \text{nums}[i]\times\text{maximum}[i-1],\ \ \text{nums}[i]\times\mathrm{minimum}[i-1]\big} $$

$$ \mathrm{minimum}[i]=\min\big{\text{nums}[i],\ \ \text{nums}[i]\times\text{minimum}[i-1],\ \ \text{nums}[i]\times\mathrm{maximum}[i-1]\big} $$

Base case： $$ \mathrm{maximum}[0]=\mathrm{minimum}[0]=\text{nums}[0] $$

基本实现

时间复杂度为 $O(N)$，空间复杂度为 $O(N)$。

class Solution {
    public int maxProduct(int[] nums) {
        int[] maximum = new int[nums.length];
        int[] minimum = new int[nums.length];
        maximum[0] = nums[0];
        minimum[0] = nums[0];
        int res = nums[0];

        for (int i = 1; i < nums.length; i++) {
            maximum[i] = Math.max(Math.max(nums[i], nums[i] * maximum[i - 1]), nums[i] * minimum[i - 1]);
            minimum[i] = Math.min(Math.min(nums[i], nums[i] * minimum[i - 1]), nums[i] * maximum[i - 1]);
            res = Math.max(res, maximum[i]);
        }

        return res;
    }
}

滚动数组实现

时间复杂度为 $O(N)$，空间复杂度为 $O(1)$。

class Solution {
    public int maxProduct(int[] nums) {
        int maximum = nums[0], minimum = nums[0], res = nums[0];

        for (int i = 1; i < nums.length; i++) {
            int tmp = maximum;
            maximum = Math.max(Math.max(nums[i], nums[i] * maximum), nums[i] * minimum);
            minimum = Math.min(Math.min(nums[i], nums[i] * minimum), nums[i] * tmp);
            res = Math.max(res, maximum);
        }

        return res;
    }
}