LeetCode 152: Maximum Product Subarray

LeetCode 2021

Problem

LeetCode 152: Maximum Product Subarray (Medium)

Problem Statement: Given an array of integers, return the largest possible product of a contiguous subarray.

Some notes:

A contiguous subarray is a range of values [i..j], where i and j are positions in the input array. For this problem, the subarray must contain at least one value (which would mean i==j). You’re not allowed to pick the subarray [] and calculate the product as 0. The one exception is when the input array is empty, in which case the correct answer is 0.
The input values are 32-bit integers (positive, negative, or zero), but they’re guaranteed to be small enough that the solution will fit in a 32-bit integer.

Solution

This is based on a solution by lee215.

The problem requires us to multiply elements of an array, so there are a few rules of multiplication to think about:

If there’s a 0 value anywhere in the subarray, the entire product is zero. So we generally want to avoid including zeros, unless the only other alternative is a negative product.
We’ll rarely be forced to settle for a negative product. If there’s only one negative element in the array, we can always exclude it unless the array only has one element. If there are two or more, we can include an even number of negative elements.

There are $O(n^2)$ contiguous subarrays in an array of length $n$. We could find the one with the largest product by checking every range [i..j] in the array, where $i \leq j$. But the rules above suggest a more efficient process:

If we’re checking all ranges that start at i and we arrive at a range [i..j] whose product is zero, there’s no reason to check any further ending j values, since the product will stay at zero forever.
If we keep track of the maximum product found so far, there are no special cases for negative elements. If the product of a range [i..j] becomes negative, then either it will become positive again when we encounter the next negative element, or if there are no negative elements remaining, we’ll just use the maximum product before we encountered the negative element.

So the key idea is: Rather than checking every starting position i and every ending position j, we can just start i at position 0 and maintain the maximum product, only moving i when the product becomes zero. That means we only need a single pass through the array. At each new j position, the product will either increase (when a[j] is positive), reset to zero (when a[j] is zero), or become negative (when a[j] is negative). In the first case, we’ll just increase the stored maximum. In the second case, we need to restart the product after the zero element. In the third case, we can just continue multiplying in case there’s another negative value coming up.

But this approach doesn’t quite work. What if our input array is [1,-2,3]? The products will be $1$, $1 \times -2 = -2$, and $-2 \times 3 = -6$. So the algorithm would return $1$ as the maximum, when it should return $3$ (for the range [2,2]).

A simple way to fix this problem is to maintain a left product that starts at position 0 and checks to the right, and a right product that starts at position len-1 and checks to the left. The answer will the maximum value found for either of these products.

Pseudocode

Variables:

a: the input array
len: the length of a
max: the maximum product
left: the product starting at the beginning of the array and moving right

right: the product starting at the end of the array and moving left

for i from 0 to len-1
    if left is 0, set it to a[i]
    else set it to left*a[i]

    if right is 0, set it to a[len-1-i]
    else set it to right*a[len-1-i]

    if left or right exceeds max, update max

return max

Code

Maximum Product Subarray on GitHub

LeetCode Model Solutions

I’m posting some LeetCode model solutions this year. For more about this, see A Project for 2021.