DSA Maximum Product Subarray

The problem

A subarray is a run of neighbouring values in a list. The maximum product subarray asks for the largest product over every such run. The run must hold at least one value.

The values may be negative or zero. A negative value can turn a bad run into a good one. That sign behaviour is the whole difficulty of the problem.

cases = [
    ([2, 3, -2, 4], 6),
    ([-2, 0, -1], 0),
    ([-2, 3, -4], 24),
    ([-1], -1),
    ([0, 2], 2),
]
for nums, expected in cases:
    print("nums", nums, "-> largest product:", expected)

The third case is the instructive one. Its answer, 24, uses the whole list, negatives included. Two negatives multiply into a positive.

Intuition: track only the largest product

The first idea tracks the largest product of a run ending at each position. Each new value either starts a fresh run or extends the best run. The idea mirrors the classic maximum-sum method.

nums = [-2, 3, -4]
high = best = nums[0]
for value in nums[1:]:
    high = max(value, high * value)
    best = max(best, high)
    print("value", value, "largest ending here:", high, "best:", best)
print("this method answers:", best)
print("the true answer is 24")

The method answers 3, and the true answer is 24. The run [-2, 3] has product -6, the worst run ending at 3. Multiplied by -4, that worst run becomes the best one, and this method had thrown it away.

Brute force: every run, counted

The brute force multiplies out every run in the list. It keeps the largest product seen. A counter records the runs examined.

def brute(nums):
    best = nums[0]
    subs = 0
    for i in range(len(nums)):
        product = 1
        for j in range(i, len(nums)):
            product *= nums[j]
            subs += 1
            best = max(best, product)
    return best, subs

for nums in [[2, 3, -2, 4], [-2, 3, -4]]:
    best, subs = brute(nums)
    print(nums, "-> largest product:", best, "runs checked:", subs)

The brute force confirms both targets, 6 and 24. Its run count grows with the square of the length. The optimal method must match these answers in one walk.

The optimal solution: track the largest and the smallest

The state is two products for runs ending at the current position, the largest and the smallest. Each new value offers three candidates, itself alone and itself times each tracked product, and the largest and smallest of the three become the new state.

Keeping the smallest is the fix for the trap above. A negative new value flips the order of the candidates. Yesterday's smallest run can become today's largest.

def max_product(nums):
    high = low = best = nums[0]
    for value in nums[1:]:
        options = (value, high * value, low * value)
        high, low = max(options), min(options)
        best = max(best, high)
    return best

cases = [
    ([2, 3, -2, 4], 6),
    ([-2, 0, -1], 0),
    ([-2, 3, -4], 24),
    ([-1], -1),
    ([0, 2], 2),
]
for nums, expected in cases:
    result = max_product(nums)
    print(nums, "->", result, "expected:", expected, "match:", result == expected)

All five cases match. A separate best value is kept apart from the two running products. The answer may sit in an early run that later values ruin, and the running pair alone would forget it.

Walkthrough: [-2, 3, -4] step by step

The walk prints the state after each value. Watch the smallest product at the second step. It carries the answer into the third step.

nums = [-2, 3, -4]
high = low = best = nums[0]
print("start:", nums[0], "largest:", high, "smallest:", low, "best:", best)
for value in nums[1:]:
    options = (value, high * value, low * value)
    high, low = max(options), min(options)
    best = max(best, high)
    print("value", value, "largest:", high, "smallest:", low, "best:", best)
print("answer:", best)

At value 3 the smallest product is -6, from the run [-2, 3]. At value -4 the candidates are -4, -12 and 24. The 24 is the old smallest, -6, times -4.

Complexity

The walk does a fixed amount of work per value, so its time is O(n). It stores three numbers, so its extra space is O(1).

The brute force checks every run. A list of n values holds n times n plus 1, divided by 2, runs, and the counter below shows that count growing.

def brute_runs(nums):
    subs = 0
    for i in range(len(nums)):
        for j in range(i, len(nums)):
            subs += 1
    return subs

for n in [4, 8, 16]:
    nums = [2] * n
    print("values", n, "- brute runs:", brute_runs(nums), " walk steps:", n - 1)

At 16 values the run count is 136 against 15 walk steps. The walk replaces the inner loop with two stored numbers.

Edge cases and pitfalls

Updating the pair in the wrong order is the classic bug. The smallest product must be computed from the old largest, not from the one just updated. The block below runs both versions on the same list.

nums = [2, 3, -2]
high = low = nums[0]
for value in nums[1:]:
    options = (value, high * value, low * value)
    high, low = max(options), min(options)
print("correct smallest after -2:", low)
high = low = nums[0]
for value in nums[1:]:
    high = max(value, high * value)
    low = min(value, high * value)
print("buggy smallest after -2:", low)

The buggy version reuses the new largest and reports -2 as the smallest. The true smallest is -12. One wrong reuse quietly corrupts every later step.

def max_product(nums):
    high = low = best = nums[0]
    for value in nums[1:]:
        options = (value, high * value, low * value)
        high, low = max(options), min(options)
        best = max(best, high)
    return best

print("single negative:", max_product([-1]))
print("zero resets the run:", max_product([-2, 0, -1]))
print("two negatives:", max_product([-2, -3]))
print("zero then positive:", max_product([0, 2]))
print("all positives:", max_product([2, 3, 4]))

A zero forces both tracked products to zero at its step. The next value starts fresh from itself. No special case handles the zero; the three candidates handle it.