Maximum Product Subarray

Today, we’ll research the LeetCode problem Maximum Product Subarray.

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

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

Like many problems, it is helpful to think about the naive solution. This solution generates all possible subsets from the input and keeps track of the max product for each subset. There are two nested loops of max length n, thus, the runtime is O(n²). This gives us a big hint that our optimal solution is not O(n²) and is probably O(nLog(n)) or O(n).

Its important to understand the intuition behind this solution, so before diving into coding, lets state some interesting things:

Fact 1: A array of all positive numbers means the max product subarray is the entire array itself. This means, the existence of numbers ≤ 0 will may cause the max subarray to be some subset of the entire input array.

Fact 2: As we multiply numbers together, it is possible to have a very large negative number multiply with another negative number to make a large number. For example: [100, -3, -8]. If we only consider [100, -3], the answer is 100 ([100]). But the inclusion of -8 at the end makes the max product 2400 ([100, -3, -8]).

This gives us a hint that as we traverse the array, we cannot just keep track of the max number, we also have to keep track of the minimum number (since this could be the new max if we come across another negative number).

Fact 3: As we traverse though our input array, from 0 to n, at any position i, we calculate the minimum product and maximum product totals given that we can include nums[i] into the existing subarray OR just take nums[i] itself. This gives us the idea of storing the maximum product and minimum product numbers for i in two separate arrays.

Fact 4: This means, as we traverse though the array, at each index i:

1. To compute the minimum value of any subarray that ends at index i, this would be the minimum of: i) nums[i] or ii) the minimum product total for up to index i-1 * nums[i] iii) the maximum product total for up to index i-1 * nums[i]
2. To compute the maximum value of any subarray that ends at index i, this would be the maximum of: i) nums[i] or ii) the minimum product total for up to index i-1 * nums[i] iii) the maximum product total for up to index i-1 * nums[i]

public int maxProduct(int[] nums) {
        int[] minValues = new int[nums.length];
        int[] maxValues = new int[nums.length];
        
        minValues[0] = nums[0];
        maxValues[0] = nums[0];
        
        int totalMaxProduct = nums[0];
        
        for(int i=1; i < nums.length; i++) {
            minValues[i] = Math.min(Math.min(minValues[i-1] * nums[i], maxValues[i-1] * nums[i]), nums[i]);
            maxValues[i] = Math.max(Math.max(minValues[i-1] * nums[i], maxValues[i-1] * nums[i]), nums[i]);     
            if (maxValues[i] > totalMaxProduct) {
                totalMaxProduct = maxValues[i];
            }
        }
        
        return totalMaxProduct;        
}

Conclusion

This solution has a time complexity of O(n). There are more memory efficient ways to implement the solution, in particular, using just two variables to keep track of the max/min product totals for the i-1^th step instead of a array(which tracks the max/min totals all values of i).

The reason why I implemented this in this fashion is to show the reasoning behind the solution and when you look at the values of maxValues and minValues in the debugger, it is more understandable when you see the entire ‘history’ of values as you iterate though the input. I will leave it to you as an exercise to reduce the memory footprint.

The most difficult part is the the intuition and thinking process behind the solution, which is omitted on many of the Youtube and websites that provide solutions to this problem and that’s why I wanted to provide this analysis.

As a FYI, this is also similar to  Largest Sum Contiguous Subarray.