Maximum Product Subarray

Difficulty: Medium Source: NeetCode

Problem

Given an integer array nums, find a subarray that has the largest product, and return the product.

Example 1: Input: nums = [2,3,-2,4] Output: 6 (subarray [2,3])

Example 2: Input: nums = [-2,0,-1] Output: 0

Constraints:

• 1 <= nums.length <= 2 * 10^4
• -10 <= nums[i] <= 10
• The product of any prefix or suffix of nums is guaranteed to fit in a 32-bit integer

Prerequisites

Before attempting this problem, you should be comfortable with:

• Kadane’s Algorithm — maximum sum subarray
• Tracking Min and Max — why we need both when negatives are involved
• Dynamic Programming — state transitions at each element

1. Brute Force

Intuition

Try every possible subarray by trying all start and end index pairs. Compute the product and track the maximum. Simple but slow.

Algorithm

1. For each starting index i:
   • Maintain a running product, extending to the right.
   • Update the global maximum at each step.
2. Return the maximum product seen.

Solution

def maxProduct_brute(nums):
    n = len(nums)
    result = nums[0]

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

    return result


print(maxProduct_brute([2, 3, -2, 4]))    # 6
print(maxProduct_brute([-2, 0, -1]))       # 0
print(maxProduct_brute([-2]))              # -2
print(maxProduct_brute([-2, 3, -4]))       # 24

Complexity

• Time: O(n²) — all pairs
• Space: O(1)

2. Dynamic Programming (Track Max and Min)

Intuition

This is like Kadane’s algorithm, but with a twist: a large negative can become a large positive if multiplied by another negative. So we must track both the maximum product and the minimum product ending at each position.

At each element:

• max_prod = max(num, num * prev_max, num * prev_min)
• min_prod = min(num, num * prev_max, num * prev_min)

The current element alone (num) handles the case of starting a fresh subarray. Multiplying by the previous max or min handles extending the existing subarray.

Algorithm

1. Initialize max_prod = min_prod = result = nums[0].
2. For each number from index 1 to n-1:
   • Compute candidates = (num, num * max_prod, num * min_prod).
   • new_max = max(candidates), new_min = min(candidates).
   • Update result = max(result, new_max).
   • Set max_prod, min_prod = new_max, new_min.
3. Return result.

Solution

def maxProduct(nums):
    max_prod = min_prod = result = nums[0]

    for num in nums[1:]:
        # Multiplying by num can flip max and min if num is negative
        candidates = (num, num * max_prod, num * min_prod)
        max_prod = max(candidates)
        min_prod = min(candidates)
        result = max(result, max_prod)

    return result


print(maxProduct([2, 3, -2, 4]))     # 6
print(maxProduct([-2, 0, -1]))        # 0
print(maxProduct([-2]))               # -2
print(maxProduct([-2, 3, -4]))        # 24  (-2 * 3 * -4 = 24)
print(maxProduct([0, 2]))             # 2
print(maxProduct([-1, -2, -9, -6]))   # 108 (-2*-9*-6... actually -2*-9=18, 18*-6=-108. -1*-2*-9=18? No: -1*-2=2, 2*-9=-18, -18*-6=108... yes 108)

Complexity

• Time: O(n) — single pass
• Space: O(1) — only three variables

Common Pitfalls

Only tracking the maximum, not the minimum. A negative minimum can become the maximum after multiplying by another negative. If you only track max_prod, you’ll miss these cases entirely.

Forgetting to consider starting a fresh subarray at the current element. Always include the bare num as a candidate. If the running products are terrible (say, due to many negatives or a zero), it’s better to start fresh.

Zeros resetting the product. When you hit a 0, both max and min become 0, effectively starting a new subarray from the next element. The num candidate in the max/min calculation handles this correctly.