152. Maximum-Product-Subarray

difficulty: Medium

Given an integer array nums, find the contiguous subarray within an array (containing at least one number) which has the largest product.

Example 1:

Input: [2,3,-2,4]
Output: 6
Explanation: [2,3] has the largest product 6.

Example 2:

Input: [-2,0,-1]
Output: 0
Explanation: The result cannot be 2, because [-2,-1] is not a subarray.

Method One

class Solution {
    public int maxProduct(int[] nums) {
        // 对于连乘这个题，有如下的观察
        // 数组中的 0，相当于把数组分成了好几个子数组来运算，因为一旦出现乘0，所有的都变0了。
        // 因此我们现在只考虑一个没有 0 的子数组。
        // 子数组中的负数，如果是偶数个，那么最大的乘积就是整个子数组。
        // 如果是奇数个，比如说有 (2k + 1) 个负数。那么必然可以分成两个子数组
        // 一个子数组是第一个负数左边的数组，另一个是第一个负数右边的子数组，有2k个负数，因此是正数。
        // 因此，最大的乘积，一定是一个这样一个没有0的子数组的prefix或者suffix。
        int lProduct = 0;
        int rProduct = 0;
        int max = Integer.MIN_VALUE;
        
        for(int i = 0; i < nums.length; i++) {
            // 这里 lProduct == 0 和 rProduct == 0 就是为了检查是不是出现了0，如果出现了就重设当前乘积为1。
            lProduct = ( lProduct == 0 ? 1 : lProduct ) * nums[i];
            rProduct = ( rProduct == 0 ? 1 : rProduct ) * nums[nums.length - i - 1];
            max = Math.max(max, Math.max(lProduct, rProduct));
        }
        return max;
    }
}
​

2022

class Solution {
    public int maxProduct(int[] nums) {
        int maxProd = Integer.MIN_VALUE;
        int curProdL = 1;
        int curProdR = 1;
        for(int i = 0; i < nums.length; i++){
            curProdL*= nums[i];
            maxProd = Math.max(maxProd, curProdL);
            if(nums[i] == 0) curProdL = 1;
        }
        for(int i = nums.length - 1; i >= 0; i--){
            curProdR *= nums[i];
            maxProd = Math.max(maxProd, curProdR);
            if(nums[i] == 0) curProdR = 1;
        }
        return maxProd;
    }
}