Maximum Product Subarray — InterviewPrepKit

Problem

Given an integer array nums, find the contiguous non-empty subarray with the largest product of its elements, and return that product. The array may contain negative numbers and zeros. The answer is guaranteed to fit in a 32-bit integer.

Examples

nums = [2,3,-2,4] → 6 — the subarray [2,3] gives 6; extending past -2 would flip the sign.
nums = [-2,0,-1] → 0 — the best non-empty product is 0 (any window with a negative alone is worse).
nums = [-2,3,-4] → 24 — the whole array: (-2)·3·(-4) = 24; two negatives make a positive.

Constraints

1 <= nums.length <= 2·10⁴
-10 <= nums[i] <= 10
Every prefix/suffix product fits in a 32-bit integer.

Think about it first

Hint 1

For a sum subarray (Kadane), you only track the best running sum. Products are trickier: a large negative running product can become the largest positive the moment you multiply by another negative. So one running value isn't enough.

Hint 2

Track two things ending at each index: the maximum product and the minimum product of a subarray ending there. A new negative number swaps their roles.

Hint 3

cur_max = max(x, x·prev_max, x·prev_min) and cur_min = min(x, x·prev_max, x·prev_min). A zero resets both (starting fresh at x handles that). Track the global best of all cur_max.

TL;DR

Track the running max and min product ending at each index (negatives swap them) — O(n) time, O(1) space.

Approach 1 — Brute force

Compute the product of every contiguous subarray and keep the largest.

def maxProduct(nums: list[int]) -> int:
    n = len(nums)
    best = nums[0]
    for i in range(n):
        prod = 1
        for j in range(i, n):
            prod *= nums[j]
            best = max(best, prod)
    return best

Complexity: O(n²) time, O(1) space. At n = 2·10⁴ that is about 4·10⁸ multiplications, too slow for the constraints.

Approach 2 — DP with max/min arrays

Unlike sums, a product can flip sign. The largest product ending at i comes from one of three candidates: nums[i] alone, nums[i]·(largest product ending at i-1), or nums[i]·(smallest product ending at i-1), because a negative times a negative is a large positive. So we carry both extremes forward.

Recurrence: hi[i] = max(nums[i], nums[i]·hi[i-1], nums[i]·lo[i-1]) lo[i] = min(nums[i], nums[i]·hi[i-1], nums[i]·lo[i-1]) Answer = max(hi).

def maxProduct(nums: list[int]) -> int:
    n = len(nums)
    hi = [0] * n
    lo = [0] * n
    hi[0] = lo[0] = nums[0]
    for i in range(1, n):
        x = nums[i]
        a, b, c = x, x * hi[i - 1], x * lo[i - 1]
        hi[i] = max(a, b, c)
        lo[i] = min(a, b, c)
    return max(hi)

Walkthrough (nums = [2,3,-2,4]):

i0: hi=2, lo=2
i1 (3): candidates 3, 6, 6 → hi=6, lo=3
i2 (-2): candidates -2, -12, -6 → hi=-2, lo=-12
i3 (4): candidates 4, -8, -48 → hi=4, lo=-48
max(hi) = max(2,6,-2,4) = 6.

Complexity: O(n) time, O(n) space.

Approach 3 — Space-optimized (two rolling variables)

Each step reads only the previous hi and lo, so keep two scalars instead of full arrays. One subtlety: cur_max must be computed from the old cur_min, so snapshot both before overwriting, or do the negative-swap first.

def maxProduct(nums: list[int]) -> int:
    best = cur_max = cur_min = nums[0]
    for x in nums[1:]:
        if x < 0:                       # negative flips the roles
            cur_max, cur_min = cur_min, cur_max
        cur_max = max(x, x * cur_max)
        cur_min = min(x, x * cur_min)
        best = max(best, cur_max)
    return best

Walkthrough (nums = [-2,3,-4]):

start best=cur_max=cur_min=-2
x=3 (≥0): cur_max=max(3,-6)=3, cur_min=min(3,-6)=-6, best=3
x=-4 (<0): swap → cur_max=-6, cur_min=3; then cur_max=max(-4,24)=24, cur_min=min(-4,-12)=-12, best=24.

Complexity: O(n) time, O(1) space.

Common pitfalls

Adapting Kadane’s max-sum idea with a single running value — a lone maximum silently drops the “two negatives make a positive” case ([-2,3,-4] → 24).
Overwriting cur_max before using the old value to compute cur_min — snapshot both, or do the negative-swap trick first.
Zeros: they force both extremes back to x (i.e. 0) via the max(x, x*prev) form, correctly restarting the subarray after the zero.
Initializing best = 0 — wrong for an all-negative single-element array like [-3]; seed from nums[0].

Pattern takeaway

When a running-optimum DP has an operation that can invert which extreme is best (multiplication by a negative, here), carry both the max and the min forward. This “track both extremes” trick generalizes Kadane’s algorithm to cases where the best future value can come from today’s worst value.