【Leetcode 热题 100】152. 乘积最大子数组

问题背景

给你一个整数数组 $nums$，请你找出数组中乘积最大的非空连续子数组（该子数组中至少包含一个数字），并返回该子数组所对应的乘积。
测试用例的答案是一个 $32$ 位 整数。

数据约束

• $1\le nums.length\le 2\times 10^4$
• $-10\le nums[i]\le 10$
• $nums$ 的任何子数组的乘积都 保证 是一个 $32$位 整数

解题过程

这题很好地适用动态规划的思想，但是不需要回溯来实现。
任何时候结果都只可能在当前乘积的最大值、最小值（负数）和当前元素本身这三者中产生。因此，只需要遍历数组并在这个过程中维护最大最小值，最后从中求得结果即可。
进一步考虑到当前的最大最小值其实只与上个状态有关，记忆化数组可以减少一个维度退化为变量。

具体实现

数组记录

class Solution {
    public int maxProduct(int[] nums) {
        int n = nums.length;
        int[] max = new int[n];
        int[] min = new int[n];
        max[0] = min[0] = nums[0];
        for (int i = 1; i < n; i++) {
            int cur = nums[i];
            max[i] = Math.max(Math.max(max[i - 1] * cur, min[i - 1] * cur), cur);
            min[i] = Math.min(Math.min(max[i - 1] * cur, min[i - 1] * cur), cur);
        }
        return Arrays.stream(max).max().getAsInt();
    }
}

空间优化

class Solution {
    public int maxProduct(int[] nums) {
        int res = Integer.MIN_VALUE;
        int max = 1;
        int min = 1;
        for (int num : nums) {
            // 注意这里需要记录当前最大值，接下来马上要更新，会影响到最小值的计算
            int curMax = max;
            max = Math.max(Math.max(curMax * num, min * num), num);
            min = Math.min(Math.min(curMax * num, min * num), num);
            res = Math.max(res, max);
        }
        return res;
    }
}