Maximum Product Subarray

You are given an integer list nums. A subarray is a non-empty run of consecutive elements.

Return the largest product that the elements of any subarray can have. Values can be negative or zero, so the best subarray is not necessarily the longest one.

The inputs are chosen so that the product of every subarray fits in a signed 32-bit integer.

Example 1

Example 2

Example 3

Constraints

• 1 <= nums.length <= 2 · 104
• -10 <= nums[i] <= 10
• The product of any subarray fits in a 32-bit signed integer

Pattern Path · Dynamic Programming · problem 154 of 169

Start simple

Multiply out every subarray starting at each index: O(n²) time.

The key idea

This is a variation of the classic maximum-subarray scan, with one twist: a negative factor flips the order of products. A very negative product ending at i - 1 becomes a very positive one if nums[i] is negative. So keep two values for each position:

• hi: the largest product of a subarray ending at the current position,
• lo: the smallest (most negative) product of a subarray ending there.

A subarray ending at x = nums[i] is either x alone or a subarray ending at i - 1 extended by x. Extending multiplies by x, which is monotone in the old product: increasing if x > 0, decreasing if x < 0. So the extremes of the extended products come from the old extremes, and

hi, lo = max(x, x·hi, x·lo), min(x, x·hi, x·lo)

(computed from the old values simultaneously). Taking x alone also covers restarting after a zero. The answer is the largest hi seen anywhere.

Each step is constant work, giving a single O(n) pass with O(1) memory.

Complexity

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

Python

class Solution:
    def maxProduct(self, nums: List[int]) -> int:
        # hi / lo: largest and smallest product of a subarray ending at the current element.
        hi = lo = best = nums[0]
        for x in nums[1:]:
            candidates = (x, x * hi, x * lo)
            hi, lo = max(candidates), min(candidates)
            best = max(best, hi)
        return best

JavaScript

var maxProduct = function(nums) {
  // hi / lo: largest and smallest product of a subarray ending at the current element.
  let hi = nums[0], lo = nums[0], best = nums[0];
  for (let i = 1; i < nums.length; i++) {
    const x = nums[i];
    const a = x * hi, b = x * lo;
    hi = Math.max(x, a, b);
    lo = Math.min(x, a, b);
    best = Math.max(best, hi);
  }
  return best;
};

What the interviewer is checking

The interviewer wants to see whether you adapt Kadane's algorithm thoughtfully, noticing that negatives require tracking the minimum as well as the maximum.

Mistakes to avoid

• Tracking only the maximum product, which loses answers like [-2, 3, -4] = 24.
• Updating hi first and then using the new hi to compute lo.
• Initialising the answer to 0, which is wrong for a list such as [-5].

Follow-ups to expect

• Return the subarray itself, not just its product? (Track start index on restarts.)
• What if products could overflow? (Logs of absolute values plus sign counting.)
• Another approach? (Best of prefix and suffix products, resetting at zeros.)

In real software

Compounded growth rates are products of factors, so finding the best stretch of consecutive returns (where some periods are losses) uses the same min/max tracking.

Practice next