Maximum Product Subarray

Given an integer array, find the contiguous subarray with the largest product. A naive O(n^2) scan is too slow.

Why this is worth learning

Multiplication can reverse ordering: a very negative product becomes very positive after another negative factor. Retain both extreme products ending at the previous index.

Before coding: one-minute experiment

For [-2,3,-4], why must the algorithm remember -6 after the second element?

Function signature

func MaxProduct(nums []int) int

Inputs / outputs

• nums: non-empty array of integers.
• Return: maximum product of any contiguous subarray.

Example

nums = [2,3,-2,4]
Best subarray: [2,3] -> 6
Output: 6

Constraints

• 1 <= len(nums) <= 100_000
• The mathematical product of every nonempty contiguous subarray is guaranteed to fit the target Go int; a representable maximum alone is insufficient.

Core idea (near-solution)

Track both maximum and minimum products ending at each position because a negative number flips signs.

Invariant: maxProd and minProd are the best/worst products ending at i.

Algorithm (step-by-step)

1. Initialize maxProd = minProd = res = nums[0].
2. For each x in nums[1:]:
   • If x < 0, swap maxProd and minProd.
   • Update maxProd = max(x, maxProd*x).
   • Update minProd = min(x, minProd*x).
   • Update res with maxProd.
3. Return res.

Correctness sketch

For a new value x, every nonempty subarray ending here is the singleton x or an extension of a prior ending subarray. Multiplication by positive x preserves order, by negative x reverses it, and by zero collapses all products to zero. Consequently the new maximum and minimum are the extrema of x, oldMaxx, and oldMinx. Swapping old extremes when x<0 lets the implementation compute these extrema with two comparisons while preserving both old values. The global answer is the maximum ending product over all endpoints. This argument assumes the products used in comparisons are representable; machine overflow would invalidate ordering.

Trace (hand walkthrough)

Example input:
nums = [2,3,-2,4]
Best subarray: [2,3] -> 6
Output: 6

Walk:
- start max=min=2, best=2
- val=3 -> max=6 min=3 best=6
- val=-2 -> max=-2 min=-12 best=6
- val=4 -> max=4 min=-48 best=6

Pitfalls to avoid

• Tracking only the max (fails with negative numbers).
• Resetting to 0 incorrectly.

Debugging lens

Test zero-separated runs, an odd and even number of negatives, and single negative values. Initialize from the first element, not zero. All tracked intermediate products—not only the final answer—must fit int.

Complexity

• Time: O(n).
• Extra space: O(1).

Implementation notes (Go)

• Swapping max/min on negative is the key correctness step.

Contract precision

The product guarantee covers the tracked minimum as well as the maximum. For example, on a 64-bit target [-9223372036854775808,2] has a representable maximum of 2 but an unrepresentable negative product, so it is outside this contract. The function has no checked-overflow result.

Reconstruction checkpoint

For [-2,3,-4], why must the algorithm remember -6 after the second element?

Return to 1D DP (Including Kadane) · Module quiz