Maximum Product Subarray

Find the largest product of a nonempty continuous subarray.

Start with the concrete trace below. It shows the state the algorithm must carry as it runs.

Problem trace

Maximum Product Subarray: Track both extreme products ending at each index because multiplying by a negative swaps which extreme can become largest.

Input and goalFind the largest product of a nonempty continuous subarray.

Initialize both extremesAt index 0, the only ending product is 2, so current_max=current_min=best=2.

scan2031-2243-14

processedPrefix[0..0]endingRange[2]arithmeticmax=2; min=2; best=2

Recognize it

Use paired extremes for contiguous products when negative values can reverse ordering and zero or a single value may force a restart.

Keep true

After each index, current_max and current_min are respectively the largest and smallest products of nonempty subarrays ending exactly there, and best is the largest current_max seen in the processed prefix.

Reuse it

When a transition is not monotone, retain every extreme that can become optimal after the next operation; sign-changing multiplication is the canonical max/min pair example.

Pattern: DP with current maximum and minimum.

Simple idea: A negative value can turn the smallest negative product into the largest positive product. Keep both extremes. Swap them before multiplying by a negative value.

def max_product_subarray(nums: list[int]) -> int:
   current_max = current_min = best = nums[0]

   for num in nums[1:]:
      if num < 0:
         current_max, current_min = current_min, current_max
      current_max = max(num, current_max * num)
      current_min = min(num, current_min * num)
      best = max(best, current_max)
   return best

Cost: $O(n)$ time and $O(1)$ space.