Reasoning Into CodeArunank Divya Sharan · Python edition← Arunank’s portfolio
Module 22 · Greedy Algorithms and Kadane-Style State

213. Maximum Product Subarray

Foundation · Download this solution · All solutions and shared helpers

Problem

Return the maximum product of a nonempty contiguous subarray of integers, or None for empty input. Zeros and negative values are allowed. Do not mutate nums. Products use Python's exact integers.

Examples

Example 1

max_product_subarray([-2,3,-4])
=> 24

The negative minimum becomes the best positive product.

Example 2

max_product_subarray([-2,0,-1])
=> 0

Zero is better than either negative singleton.

Example 3

max_product_subarray([])
=> None

The empty list has no nonempty product interval.

Reveal the worked solution and reasoning

Why this mechanism works

Multiplication by a negative value reverses order: the smallest previous ending product can become the largest new one. Therefore preserve both extremes. At each position compare starting anew with extending either old extreme, computing both new states before overwriting the old ones.

State and boundaries

high and low are the maximum and minimum products of nonempty subarrays ending at the previous index. best is the maximum over all completed endpoints.

Protocol

  1. Initialize both extremes and best from the first value.
  2. Form candidates current, old_high*current, old_low*current.
  3. Assign new high and low from their maximum and minimum.
  4. Update best.

Visualization

[-2,3,-4]
after 3: high=3, low=-6
multiply by -4: old low becomes 24
new maximum comes from the former minimum

Python implementation

def max_product_subarray(nums):
    if not nums:
        return None
    high = low = best = nums[0]
    for i in range(1, len(nums)):
        value = nums[i]
        candidates = (value, high * value, low * value)
        high, low = max(candidates), min(candidates)
        best = max(best, high)
    return best

Worked execution

Recorded state changes after statements; L numbers refer to the solution file. Long traces are explicitly condensed.

max_product_subarray([-2,3,-4])

L2 max_product_subarray: if not nums:
nums=[-2, 3, -4]

L4 max_product_subarray: high = low = best = nums[0]
nums=[-2, 3, -4]; high=-2; low=-2; best=-2

L5 max_product_subarray: for i in range(1, len(nums)):
nums=[-2, 3, -4]; high=-2; low=-2; best=-2; i=1

L6 max_product_subarray: value = nums[i]
nums=[-2, 3, -4]; high=-2; low=-2; best=-2; i=1; value=3

L7 max_product_subarray: candidates = (value, high * value, low * value)
nums=[-2, 3, -4]; high=-2; low=-2; best=-2; i=1; value=3; candidates=(3, -6, -6)

L8 max_product_subarray: high, low = max(candidates), min(candidates)
nums=[-2, 3, -4]; high=3; low=-6; best=-2; i=1; value=3; candidates=(3, -6, -6)

L9 max_product_subarray: best = max(best, high)
nums=[-2, 3, -4]; high=3; low=-6; best=3; i=1; value=3; candidates=(3, -6, -6)

L5 max_product_subarray: for i in range(1, len(nums)):
nums=[-2, 3, -4]; high=3; low=-6; best=3; i=2; value=3; candidates=(3, -6, -6)

L6 max_product_subarray: value = nums[i]
nums=[-2, 3, -4]; high=3; low=-6; best=3; i=2; value=-4; candidates=(3, -6, -6)

L7 max_product_subarray: candidates = (value, high * value, low * value)
nums=[-2, 3, -4]; high=3; low=-6; best=3; i=2; value=-4; candidates=(-4, -12, 24)

L8 max_product_subarray: high, low = max(candidates), min(candidates)
nums=[-2, 3, -4]; high=24; low=-12; best=3; i=2; value=-4; candidates=(-4, -12, 24)

L9 max_product_subarray: best = max(best, high)
nums=[-2, 3, -4]; high=24; low=-12; best=24; i=2; value=-4; candidates=(-4, -12, 24)

Result: 24. The negative minimum becomes the best positive product.

max_product_subarray([-2,0,-1])

L2 max_product_subarray: if not nums:
nums=[-2, 0, -1]

L4 max_product_subarray: high = low = best = nums[0]
nums=[-2, 0, -1]; high=-2; low=-2; best=-2

L5 max_product_subarray: for i in range(1, len(nums)):
nums=[-2, 0, -1]; high=-2; low=-2; best=-2; i=1

L6 max_product_subarray: value = nums[i]
nums=[-2, 0, -1]; high=-2; low=-2; best=-2; i=1; value=0

L7 max_product_subarray: candidates = (value, high * value, low * value)
nums=[-2, 0, -1]; high=-2; low=-2; best=-2; i=1; value=0; candidates=(0, 0, 0)

L8 max_product_subarray: high, low = max(candidates), min(candidates)
nums=[-2, 0, -1]; high=0; low=0; best=-2; i=1; value=0; candidates=(0, 0, 0)

L9 max_product_subarray: best = max(best, high)
nums=[-2, 0, -1]; high=0; low=0; best=0; i=1; value=0; candidates=(0, 0, 0)

L5 max_product_subarray: for i in range(1, len(nums)):
nums=[-2, 0, -1]; high=0; low=0; best=0; i=2; value=0; candidates=(0, 0, 0)

L6 max_product_subarray: value = nums[i]
nums=[-2, 0, -1]; high=0; low=0; best=0; i=2; value=-1; candidates=(0, 0, 0)

L7 max_product_subarray: candidates = (value, high * value, low * value)
nums=[-2, 0, -1]; high=0; low=0; best=0; i=2; value=-1; candidates=(-1, 0, 0)

L8 max_product_subarray: high, low = max(candidates), min(candidates)
nums=[-2, 0, -1]; high=0; low=-1; best=0; i=2; value=-1; candidates=(-1, 0, 0)

Result: 0. Zero is better than either negative singleton.

Why the solution is correct

Every ending subarray is a singleton or an extension. Multiplication by a fixed value maps the range of previous products monotonically or reverse-monotonically, so its extrema arise from the old high or low. Considering those and the singleton yields both exact new extremes, including zero resets.

Time and space

O(n) arithmetic operations and O(1) integer variables. Exact product bit lengths can grow with n, so arithmetic time and bit storage are not constant for unbounded integers.

Common mistakes

Keeping only the maximum loses negative products that later become positive. Updating high before computing low can use the same element twice.

Reasoning card

State: high and low are the maximum and minimum products of nonempty subarrays ending at the previous index. best is the maximum over all completed endpoints.

Invariant: Two ending states cover all sign possibilities.

Decision to rehearse: Track both maximum and minimum ending here because negatives swap roles.

Finish: Update best

Transfer exercise

Track the intervals associated with both extremes, paying attention to which old interval each new candidate extends.