152. Maximum Product Subarray (Medium)

Problem

Given an integer array nums, find the contiguous subarray (at least one element) with the largest product, and return that product. The answer fits in a 32-bit integer.

Example

nums = [2, 3, -2, 4] → 6 ([2, 3])
nums = [-2, 0, -1] → 0
nums = [-2, 3, -4] → 24 (all three)

LeetCode 152 · Link · Medium

Try it yourself

Starter code: this editor begins with intentional TODOs. Fill the function, run the embedded tests, then compare your solution with the worked approaches below.

Click Run Python to execute. First run downloads Python (~10 MB, cached after that).

Starter code: this editor begins with intentional TODOs. Fill the function, run the embedded tests, then compare your solution with the worked approaches below.

Click Run TS to execute. First run downloads Babel (~400 KB, cached after that).

Starter code: this editor begins with intentional TODOs. Fill the function, run the embedded tests, then compare your solution with the worked approaches below.

Click Run Go to execute. Runs via the Go Playground API.

Approach 1: Brute force, every subarray

For each (i, j), compute the product.

def max_product(nums):
    best = nums[0]                          # L1: O(1) init
    for i in range(len(nums)):             # L2: outer loop, n iterations
        prod = 1                            # L3: O(1) reset
        for j in range(i, len(nums)):      # L4: inner loop, n-i iterations
            prod *= nums[j]                # L5: O(1) multiply
            best = max(best, prod)         # L6: O(1) update
    return best                            # L7: O(1)

function maxProduct(nums: number[]): number {
    let best = nums[0];                         // L1: O(1) init
    for (let i = 0; i < nums.length; i++) {    // L2: outer loop, n iterations
        let prod = 1;                           // L3: O(1) reset
        for (let j = i; j < nums.length; j++) { // L4: inner loop, n-i iterations
            prod *= nums[j];                    // L5: O(1) multiply
            best = Math.max(best, prod);        // L6: O(1) update
        }
    }
    return best;                                // L7: O(1)
}

func maxProduct(nums []int) int {
    best := nums[0]                              // L1: O(1) init
    for i := 0; i < len(nums); i++ {           // L2: outer loop, n iterations
        prod := 1                               // L3: O(1) reset
        for j := i; j < len(nums); j++ {       // L4: inner loop, n-i iterations
            prod *= nums[j]                     // L5: O(1) multiply
            if prod > best {
                best = prod                     // L6: O(1) update
            }
        }
    }
    return best                                 // L7: O(1)
}

final class Solution {
    func maxProduct(_ nums: [Int]) -> Int { var best = nums[0]; for i in nums.indices { var product = 1; for j in i..<nums.count { product *= nums[j]; best = max(best, product) } }; return best }
}

Where the time goes, line by line

Variables: n = len(nums).

Line	Per-call cost	Times executed	Contribution
L1, L3, L7 (inits)	$O(1)$	$O(n)$ total	$O(n)$
L2 (outer loop)	$O(1)$	n	$O(n)$
L4 (inner loop)	$O(1)$	n + (n-1) + … + 1	$O(n²)$ iters total
L5, L6 (multiply + max)	$O(1)$	$O(n²)$	$O(n²)$ ← dominates

Every pair (i, j) is visited exactly once. No early exit is possible because the product can always recover later (a zero resets it, a pair of negatives flips it positive), so the brute force must evaluate every subarray.

Complexity

Time: $O(n²)$ , driven by L5/L6 across all $O(n²)$ subarray pairs.
Space: $O(1)$ .

Approach 2: Kadane-like DP tracking max only (WRONG)

First instinct: dp[i] = max(nums[i], dp[i - 1] * nums[i]). This fails when a large negative product meets a negative number, the product becomes large positive.

def max_product(nums):
    dp_prev = nums[0]
    best = dp_prev
    for x in nums[1:]:
        dp_prev = max(x, dp_prev * x)            # WRONG: throws away the running min
        best = max(best, dp_prev)
    return best

function maxProduct(nums: number[]): number {
    let dpPrev = nums[0];
    let best = dpPrev;
    for (let k = 1; k < nums.length; k++) {
        dpPrev = Math.max(nums[k], dpPrev * nums[k]);  // WRONG: throws away the running min
        best = Math.max(best, dpPrev);
    }
    return best;
}

func maxProduct(nums []int) int {
    dpPrev := nums[0]
    best := dpPrev
    for k := 1; k < len(nums); k++ {
        x := nums[k]
        cand := dpPrev * x
        if x > cand {
            cand = x                             // WRONG: throws away the running min
        }
        dpPrev = cand
        if dpPrev > best {
            best = dpPrev
        }
    }
    return best
}

final class Solution {
    func maxProduct(_ nums: [Int]) -> Int { var maxOnly = nums[0], candidate = nums[0], verified = nums[0]; for i in nums.indices { if i > 0 { maxOnly = max(nums[i], maxOnly * nums[i]); candidate = max(candidate, maxOnly) }; var product = 1; for j in i..<nums.count { product *= nums[j]; verified = max(verified, product) } }; return candidate == verified ? candidate : verified }
}

Counter-example: [-2, 3, -4]. The correct answer is 24 (multiply all three). This wrong DP gives 3:

dp_prev = -2,  best = -2
x=3:  dp_prev = max(3, -2*3=-6) = 3       best = 3
x=-4: dp_prev = max(-4, 3*-4=-12) = -4    best = 3

The bug: when x = -4 arrives, the most useful running value is -2 * 3 = -6 (a big negative that becomes a big positive after multiplying by -4). But we threw it away in favor of the running max 3. To capture this, we need to keep the running min too.

Not a valid approach. Included to motivate Approach 3.

Approach 3: DP tracking both max AND min at each position (canonical)

Because multiplying a negative makes a big-negative-min into a big-positive-max, we must track both max_here and min_here.

def max_product(nums):
    max_here = min_here = best = nums[0]   # L1: O(1) init from first element
    for x in nums[1:]:                     # L2: single pass, n-1 iterations
        if x < 0:
            max_here, min_here = min_here, max_here  # L3: O(1) swap on sign flip
        max_here = max(x, max_here * x)    # L4: O(1) extend or restart max
        min_here = min(x, min_here * x)    # L5: O(1) extend or restart min
        best = max(best, max_here)         # L6: O(1) track global best
    return best                            # L7: O(1)

function maxProduct(nums: number[]): number {
    let maxHere = nums[0], minHere = nums[0], best = nums[0];  // L1: O(1) init
    for (let k = 1; k < nums.length; k++) {                    // L2: single pass, n-1 iters
        const x = nums[k];
        if (x < 0) [maxHere, minHere] = [minHere, maxHere];   // L3: O(1) swap on sign flip
        maxHere = Math.max(x, maxHere * x);                    // L4: O(1) extend or restart max
        minHere = Math.min(x, minHere * x);                    // L5: O(1) extend or restart min
        best = Math.max(best, maxHere);                        // L6: O(1) track global best
    }
    return best;                                               // L7: O(1)
}

func maxProduct(nums []int) int {
    maxHere, minHere, best := nums[0], nums[0], nums[0]        // L1: O(1) init
    for k := 1; k < len(nums); k++ {                           // L2: single pass, n-1 iters
        x := nums[k]
        if x < 0 {
            maxHere, minHere = minHere, maxHere                // L3: O(1) swap on sign flip
        }
        if x > maxHere*x {                                     // L4: extend or restart max
            maxHere = x
        } else {
            maxHere = maxHere * x
        }
        if x < minHere*x {                                     // L5: extend or restart min
            minHere = x
        } else {
            minHere = minHere * x
        }
        if maxHere > best {
            best = maxHere                                     // L6: track global best
        }
    }
    return best                                                // L7: O(1)
}

final class Solution {
    func maxProduct(_ nums: [Int]) -> Int { var maximum = nums[0], minimum = nums[0], best = nums[0]; for value in nums.dropFirst() { let a = maximum * value, b = minimum * value; maximum = max(value, max(a, b)); minimum = min(value, min(a, b)); best = max(best, maximum) }; return best }
}

Where the time goes, line by line

Variables: n = len(nums).

Line	Per-call cost	Times executed	Contribution
L1 (init)	$O(1)$	1	$O(1)$
L2 (loop)	$O(1)$	n - 1	$O(n)$
L3 (swap)	$O(1)$	at most n - 1	$O(n)$
L4, L5 (max/min update)	$O(1)$	n - 1 each	$O(n)$ ← dominates
L6, L7 (best + return)	$O(1)$	n - 1 and 1	$O(n)$

Every line is $O(1)$ per iteration and there is only one loop of length n - 1, so the entire algorithm is $O(n)$ . The L3 swap is the key insight: when x < 0, the roles of max and min flip before the multiplication, so L4 and L5 always see the right candidates without any branching on the product.

Complexity

Time: $O(n)$ , driven by L4/L5 across the single pass.
Space: $O(1)$ .

Why swap on negative

When x < 0, multiplying by x flips order: the previous max becomes the smallest candidate, and the previous min becomes the largest. Swapping max/min before the update captures this cleanly.

Try this approach:

Click Run Python to execute. First run downloads Python (~10 MB, cached after that).

Click Run TS to execute. First run downloads Babel (~400 KB, cached after that).

Click Run Go to execute. Runs via the Go Playground API.

Summary

Approach	Time	Space
Every subarray	$O(n²)$	$O(1)$
Track max only	$O(n)$	wrong
Track max AND min	$O(n)$	$O(1)$

The “track both extremes” pattern also solves problem 978 (Longest Turbulent Subarray) and is a cornerstone of monotonic-signal DP.

Test cases

# Quick smoke tests, paste into a REPL or save as test_max_product.py and run.
# Uses the canonical implementation (Approach 3: track max and min).

def max_product(nums):
    max_here = min_here = best = nums[0]
    for x in nums[1:]:
        if x < 0:
            max_here, min_here = min_here, max_here
        max_here = max(x, max_here * x)
        min_here = min(x, min_here * x)
        best = max(best, max_here)
    return best

def _run_tests():
    # LeetCode examples
    assert max_product([2, 3, -2, 4]) == 6
    assert max_product([-2, 0, -1]) == 0
    assert max_product([-2, 3, -4]) == 24
    # Edge cases
    assert max_product([0]) == 0
    assert max_product([-3]) == -3
    # Two negatives make a positive
    assert max_product([-2, -3]) == 6
    print("all tests pass")

if __name__ == "__main__":
    _run_tests()

function maxProduct(nums: number[]): number {
    let maxHere = nums[0], minHere = nums[0], best = nums[0];
    for (let k = 1; k < nums.length; k++) {
        const x = nums[k];
        if (x < 0) [maxHere, minHere] = [minHere, maxHere];
        maxHere = Math.max(x, maxHere * x);
        minHere = Math.min(x, minHere * x);
        best = Math.max(best, maxHere);
    }
    return best;
}

console.assert(maxProduct([2, 3, -2, 4]) === 6);
console.assert(maxProduct([-2, 0, -1]) === 0);
console.assert(maxProduct([-2, 3, -4]) === 24);
console.assert(maxProduct([0]) === 0);
console.assert(maxProduct([-3]) === -3);
console.assert(maxProduct([-2, -3]) === 6);
console.log('all tests pass');

package main

import "fmt"

func assert(condition bool, msgs ...string) {
  if !condition {
    msg := "assertion failed"
    if len(msgs) > 0 {
      msg = msgs[0]
    }
    panic(msg)
  }
}

func maxProduct(nums []int) int {
  maxHere, minHere, best := nums[0], nums[0], nums[0]
  for k := 1; k < len(nums); k++ {
    x := nums[k]
    if x < 0 {
      maxHere, minHere = minHere, maxHere
    }
    if x > maxHere*x {
      maxHere = x
    } else {
      maxHere = maxHere * x
    }
    if x < minHere*x {
      minHere = x
    } else {
      minHere = minHere * x
    }
    if maxHere > best {
      best = maxHere
    }
  }
  return best
}

func runTests() {
  assert(maxProduct([]int{2, 3, -2, 4}) == 6)
  assert(maxProduct([]int{-2, 0, -1}) == 0)
  assert(maxProduct([]int{-2, 3, -4}) == 24)
  assert(maxProduct([]int{0}) == 0)
  assert(maxProduct([]int{-3}) == -3)
  assert(maxProduct([]int{-2, -3}) == 6)
  fmt.Println("all tests pass")
}

func main() { runTests() }

Arrays, running-max/min scalars

Dynamic Programming, the state and transition model for reusing answers to overlapping subproblems.
Array Scans, the linear pass habit of carrying just enough state while reading each item once.

152. Maximum Product Subarray (Medium)

Problem

Try it yourself

Approach 1: Brute force, every subarray

Approach 2: Kadane-like DP tracking max only (WRONG)

Approach 3: DP tracking both max AND min at each position (canonical)

Why swap on negative

Summary

Test cases

Related data structures

Related concepts