Poison

152. Maximum Product Subarray

发表于 
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
class Solution {
    public int maxProduct(int[] nums) {
        int[] maxProducts = new int[nums.length];
        int[] minProducts = new int[nums.length];

        maxProducts[0] = minProducts[0] = nums[0];
        int maxProduct = maxProducts[0];
        for (int i = 1; i < nums.length; i++) {
            // 注意乘积最大子数组不一定以 nums[0] 开始，如：[0, 2] 对应的乘积最大子数组为 [2], 所以下方单独处理了 nums[i], 以便之前的乘积为 0 时丢弃掉之前的子数组
            maxProducts[i] = Math.max(Math.max(nums[i] * maxProducts[i - 1], nums[i] * minProducts[i - 1]), nums[i]);
            minProducts[i] = Math.min(Math.min(nums[i] * maxProducts[i - 1], nums[i] * minProducts[i - 1]), nums[i]);
            maxProduct = Math.max(maxProduct, maxProducts[i]);
        }

        return maxProduct;
    }
}
Reference

152. Maximum Product Subarray