Question Link

https://leetcode.com/problems/maximum-product-subarray/

Question Description

Given an array, return the maximum product that can be computed from subarray.
Input: nums = [2,3,-2,4,-2]
Output: 96
Input: nums = [2,3,-2,4]
Output: 6
Input: nums = [-2,0,-1]
Output: 0

Simulation

Case1 :- All the elements are positive - return Product of all the elements in the array
Case2 :- Array have even number of negative elements - return
Case3 :- Array have odd number of negative elements.
Case4 :- Array also contains 0

Solution 1: Array Traversing

Maintaining Max, Min and Res Variable. The golbal max is computed with either Max or Min * (Negative Number)

Solution 2: Array Traversing Optimized

Based on the above solution, we notices that when multiple negative number, we swap the min and max to avoid additional computation.

Solution 3: Two Pointers+ Prefix/Sufix

Implementation

Solution 1: Array Traversing

public int maxProduct(int[] nums) {
    int max = nums[0], min = nums[0], ans = nums[0];
    for (int i = 1; i < nums.length; i++) {
        int temp = max; // store the max because before updating min your max will already be updated
        max = Math.max(Math.max(max * nums[i], min * nums[i]), nums[i]);
        min = Math.min(Math.min(temp * nums[i], min * nums[i]), nums[i]);
        if (max > ans) {
            ans = max;
        }
    }
    return ans;
}

Solution 2: Array Traversing Optimized

public int maxProduct(int[] nums) {
    int max = nums[0], min = nums[0], ans = nums[0];
    int n = nums.length;
    for (int i = 1; i < n; i++) {
        // Swapping min and max
        if (nums[i] < 0) {
            int temp = max;
            max = min;
            min = temp;
        }
        max = Math.max(nums[i], max * nums[i]);
        min = Math.min(nums[i], min * nums[i]);
        ans = Math.max(ans, max);
    }
    return ans;
}

Solution 3: Two Pointers + Prefix/Surfix

public int maxProduct(int[] nums) {
    int n = nums.length;
    int l = 1, r = 1;
    int ans = nums[0];
    for (int i = 0; i < n; i++) {
        //if any of l or r become 0 then update it to 1
        l = l == 0 ? 1 : l;
        r = r == 0 ? 1 : r;
        l *= nums[i]; //prefix product
        r *= nums[n - 1 - i]; //suffix product
        ans = Math.max(ans, Math.max(l, r));
    }
    return ans;
}