152. 乘积最大子数组

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

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

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

示例 1:

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

示例 2:

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

提示:

• 1 <= nums.length <= 2 * 104
• -10 <= nums[i] <= 10
• nums 的任何前缀或后缀的乘积都 保证 是一个 32-位 整数

动态规划

为了处理当前数是负数的情况，需要考虑前面数组的最大元素乘积和最小元素乘积。

这道题和 53. 最大子数组和 有点像，那道题定义的 dp 数组是： dp[i] 记录以 nums[i] 为结尾的「最大子数组和」，从而写出状态转移方程。

这道题可以采用类似的思路，但需要注意的是，在 53 题中，子数组 nums[0..i] 的最大元素和是由 nums[0..i-1] 的最大元素和推导出的， 但本题变成子数组的乘积则不一定。

比如 nums[i] = -1，nums[0..i-1] 子数组的最大元素乘积为 10， 那么我能不能说 nums[0..i] 的最大元素乘积为 max(-1, -1 * 10) = -1 呢？

其实不行，因为可能nums[0..i-1] 子数组的最小元素乘积为 -6，那么 nums[0..i] 的最大元素乘积应该为 max(-1, -1 * 10, -1 * -6) = 6`。

所以这道题和 53 题的最大区别在于，要同时维护「以 nums[i] 结尾的最大子数组」和「以 nums[i] 结尾的最小子数组」，以便适配 nums[i] 可能为负的情况。

class Solution {
    public int maxProduct(int[] nums) {
        int n = nums.length;
        // 定义：dp1[i] 是以 nums[i] 结尾的子数组的最小乘积
        int[] dp1 = new int[n];
        // 定义：dp2[i] 是以 nums[i] 结尾的子数组的最大乘积
        int[] dp2 = new int[n];

        // base case
        dp1[0] = nums[0];
        dp2[0] = nums[0];
        // 状态转移方程
        for (int i = 1; i < n; i++) {
            // 计算以 nums[i] 结尾的子数组的最小乘积。重点。
            dp1[i] = min(dp1[i - 1] * nums[i], dp2[i - 1] * nums[i], nums[i]);
            // 计算以 nums[i] 结尾的子数组的最大乘积
            dp2[i] = max(dp1[i - 1] * nums[i], dp2[i - 1] * nums[i], nums[i]);
        }

        // 遍历所有子数组的最大乘积，求最大值
        int res = Integer.MIN_VALUE;
        for (int i = 0; i < n; i++) {
            res = Math.max(res, dp2[i]);
        }
        return res;
    }

    int min(int a, int b, int c) {
        return Math.min(Math.min(a, b), c);
    }

    int max(int a, int b, int c) {
        return Math.max(Math.max(a, b), c);
    }
}

易得这里的渐进时间复杂度和渐进空间复杂度都是 O(n)。

滚动更新

class Solution {
    public int maxProduct(int[] nums) {
        int n = nums.length;
        // base case
        int prevMin = nums[0];
        int prevMax = nums[0];
        int res = nums[0];

        // 状态转移方程
        for (int i = 1; i < n; i++) {
            int currMin = min(prevMin * nums[i], prevMax * nums[i], nums[i]);
            int currMax = max(prevMin * nums[i], prevMax * nums[i], nums[i]);
            // 更新结果
            res = Math.max(res, currMax);
            // 更新 prevMin 和 prevMax
            prevMin = currMin;
            prevMax = currMax;
        }

        return res;
    }

    int min(int a, int b, int c) {
        return Math.min(Math.min(a, b), c);
    }

    int max(int a, int b, int c) {
        return Math.max(Math.max(a, b), c);
    }
}

• 时间复杂度：程序一次循环遍历了 nums，故渐进时间复杂度为 O(n)。
• 空间复杂度：优化后只使用常数个临时变量作为辅助空间，与 n 无关，故渐进空间复杂度为 O(1)。