Maximum Product Subarray — Leetcode 152

Original problem link: https://leetcode.com/problems/maximum-product-subarray/description/

In this problem, we’re given an array of numbers ranging from -10 to 10 and asked to compute the maximum product of any subarray.

The key thing in this problem is to remember that unlike in maximum subarray sum, products can go from large to small to large again when there are negative numbers involved. So we need to keep track of both the min and max products we have seen.

class Solution {
    public int maxProduct(int[] nums) {
        // to accomodate the fact that two negatives can multiply to be a positive, so we have to track min products as well
        int[] maxProds = new int[nums.length];
        int[] minProds = new int[nums.length];
        maxProds[0] = nums[0];
        minProds[0] = nums[0];

        for (int i = 1; i < nums.length; i++) {
            maxProds[i] = Math.max(nums[i], Math.max(nums[i] * maxProds[i - 1], nums[i] * minProds[i - 1]));
            minProds[i] = Math.min(nums[i], Math.min(nums[i] * maxProds[i - 1], nums[i] * minProds[i - 1]));
        }

        int result = Integer.MIN_VALUE;
        for (int i = 0; i < nums.length; i++) {
            result = Math.max(result, maxProds[i]);
        }
        return result;
    }
}

The runtime is 1 ms and it beats 94% of submissions.