LeetCode: 152. Maximum Product Subarray

2026-03-21

Track both the minimum and maximum products at each step to solve the problem in O(N) time.

152. Maximum Product Subarray

152. Maximum Product Subarray

Summary

Given an integer array nums, find the subarray that has the largest product and return that product.

Approach

Use dynamic programming.

There are two states at the i-th value:

  • the minimum product ending at the current position
  • the maximum product ending at the current position

We choose these values from:

  • the current value itself
  • prev_min * current value
  • prev_max * current value

We need to track the minimum product as well, because when the current value is negative, multiplying it by the previous minimum product can produce the new maximum product.

Function

Initialization:

  • max_prefix = nums[0]
  • min_prefix = nums[0]
  • best = nums[0]

For each number n in nums[1:]:

  • values = [n, n * max_prefix, n * min_prefix]
  • max_prefix = max(values)
  • min_prefix = min(values)
  • best = max(best, max_prefix)

Return best.

Complexity

Time complexity: O(N) Space complexity: O(1)