Back to solutions

Maximum Product Subarray

MediumArrays

Find the largest product of any contiguous subarray.

Open problem
Constraints
  • 1 <= n <= 2*10^4
  • -10 <= nums[i] <= 10
  • answer fits in 32 bits

Track running max and min

Time O(n)Space O(1)

A negative number flips the sign, so the largest product can come from the smallest (most negative) product so far. Keep both the max and min product ending at the current index. When the current value is negative, swap them before updating, because multiplying by a negative turns the smallest into the largest.

Key terms
running max / min:
The largest and smallest products of subarrays ending at the current index.
sign flip:
Multiplying by a negative number turns a minimum into a maximum and vice versa.
int maxProduct(vector<int>& nums) {
    int best = nums[0], mx = nums[0], mn = nums[0];
    for (size_t i = 1; i < nums.size(); i++) {
        int x = nums[i];
        if (x < 0) swap(mx, mn);
        mx = max(x, mx * x);
        mn = min(x, mn * x);
        best = max(best, mx);
    }
    return best;
}
Step by step
  1. Initialise best, mx, mn all to nums[0].
  2. For each next value x, if x is negative swap mx and mn (the extremes swap roles).
  3. Update mx = max(x, mx*x) and mn = min(x, mn*x) either start fresh at x or extend.
  4. Update best = max(best, mx). Return best after the scan.