LeetCode 152: Maximum Product Subarray

Problem Restatement

We are given an integer array nums.

We need to find a contiguous non-empty subarray whose product is as large as possible.

Return the maximum product.

A subarray must contain consecutive elements from the original array.

For example:

nums = [2, 3, -2, 4]

The subarray:

[2, 3]

has product:

2 * 3 = 6

The full array product is:

2 * 3 * -2 * 4 = -48

So the answer is:

6

Input and Output

Example function shape:

def maxProduct(nums: list[int]) -> int:
    ...

Examples

Example 1:

nums = [2, 3, -2, 4]

Possible products:

The largest product is:

6

Example 2:

nums = [-2, 0, -1]

Possible products:

The maximum product is:

0

Example 3:

nums = [-2, 3, -4]

The full product is:

(-2) * 3 * (-4) = 24

So the answer is:

24

First Thought: Brute Force

The simplest solution is to try every possible subarray.

For every starting position i, compute the product while extending the subarray to the right.

Code:

class Solution:
    def maxProduct(self, nums: list[int]) -> int:
        n = len(nums)
        best = nums[0]

        for i in range(n):
            product = 1

            for j in range(i, n):
                product *= nums[j]
                best = max(best, product)

        return best

This works because every contiguous subarray is checked exactly once.

Problem With Brute Force

If the array has n elements, there are about:

possible subarrays.

So the brute force algorithm runs in:

O(n^2)

time.

We need a faster method.

Key Insight

This problem becomes tricky because of negative numbers.

A negative number can completely change the result.

For example:

2 * 3 = 6

but:

2 * 3 * (-2) = -12

Then multiplying by another negative number flips the sign again:

2 * 3 * (-2) * (-4) = 48

So while scanning the array, we must track:

1. The largest product ending at the current position
2. The smallest product ending at the current position

The smallest product matters because multiplying two negative numbers can become a very large positive number.

Dynamic Programming State

At each index:

When we read a new number x, three possibilities exist:

1. Start a new subarray with x
2. Extend the previous maximum product
3. Extend the previous minimum product

So the transitions are:

and:

Algorithm

Initialize:

max_prod = nums[0]
min_prod = nums[0]
answer = nums[0]

Then scan from left to right.

For each number:

1. Compute possible products
2. Update maximum product ending here
3. Update minimum product ending here
4. Update global answer

Correctness

At every position i, max_prod stores the largest product among all subarrays ending at index i.

Similarly, min_prod stores the smallest product among all subarrays ending at index i.

Any subarray ending at i must either:

1. Start at i
2. Extend a subarray ending at i - 1

Therefore the only possible products are:

nums[i]
nums[i] * previous_max
nums[i] * previous_min

Taking the maximum of these gives the best product ending at i.

Taking the minimum gives the worst product ending at i.

Because every subarray must end somewhere, tracking the best value across all positions guarantees the global maximum product.

Complexity

Implementation

class Solution:
    def maxProduct(self, nums: list[int]) -> int:
        max_prod = nums[0]
        min_prod = nums[0]
        answer = nums[0]

        for num in nums[1:]:
            candidates = (
                num,
                num * max_prod,
                num * min_prod,
            )

            max_prod = max(candidates)
            min_prod = min(candidates)

            answer = max(answer, max_prod)

        return answer

Code Explanation

We begin with the first number:

max_prod = nums[0]
min_prod = nums[0]
answer = nums[0]

For every next number, we compute all possible ways to form a subarray ending here:

candidates = (
    num,
    num * max_prod,
    num * min_prod,
)

A negative number may turn the previous minimum into the new maximum.

So we must compute both.

Then we update:

max_prod = max(candidates)
min_prod = min(candidates)

Finally:

answer = max(answer, max_prod)

stores the best result seen so far.

Alternative Optimization

Some implementations swap the variables when the current number is negative.

Example:

if num < 0:
    max_prod, min_prod = min_prod, max_prod

Then:

max_prod = max(num, num * max_prod)
min_prod = min(num, num * min_prod)

This avoids creating a temporary tuple.

Both versions are correct.

Testing

def run_tests():
    sol = Solution()

    assert sol.maxProduct([2, 3, -2, 4]) == 6
    assert sol.maxProduct([-2, 0, -1]) == 0
    assert sol.maxProduct([-2, 3, -4]) == 24
    assert sol.maxProduct([0, 2]) == 2
    assert sol.maxProduct([-2]) == -2
    assert sol.maxProduct([-1, -2, -3]) == 6
    assert sol.maxProduct([2, -5, -2, -4, 3]) == 24

    print("all tests passed")

run_tests()