Maximum Product Subarray

Hard · rating 1600 · Dynamic Programming, Arrays

The first line contains n. The second line contains n integers. Print the maximum product of any non-empty contiguous subarray.

Constraints: 1 ≤ n ≤ 104

Editorial

Maximum Product Subarray is a well-known array/DP interview problem and a subtle twist on Maximum Subarray: a negative value can flip the sign, so the smallest (most negative) running product matters too.

Approach

Track both the maximum and minimum product ending at the current index. On a negative number the previous min becomes the new max and vice versa, so swap them before updating.

best = hi = lo = nums[0]
for x in nums[1:]:
    if x < 0: hi, lo = lo, hi
    hi = max(x, hi * x)
    lo = min(x, lo * x)
    best = max(best, hi)
return best

Complexity

Time: O(n). Space: O(1).

Related problems

Open Maximum Product Subarray in Code Arena →