Skip to content

137 — Maximum Product Subarray

Jump to bottom
rebeloper edited this page Jul 14, 2026 · 4 revisions

137 — Maximum Product Subarray

LeetCode 152 · Medium. Given an integer array nums, find a subarray that has the largest product, and return the product. The test cases are generated so that the answer fits in a 32-bit integer.

🍽️ Intuition

Maximum Subarray Sum would be easy DP — the best sum ending at i is either nums[i] alone or nums[i] plus the best sum ending at i-1. Products break that logic in one specific way: multiplying by a negative number flips which running value is best. The most negative product seen so far, multiplied by another negative number, can suddenly become the largest product around — so tracking only a running max ending at each position isn't enough. You have to drag along the running minimum too, because today's minimum might be tomorrow's maximum the instant a negative number shows up.

🚩 Pattern-Recognition Cue

"Largest product of a contiguous subarray" with an array that can contain negative numbers (and possibly zeros) is the cue for tracking two running values instead of one: a running max and a running min ending at each position, because a negative multiplier can swap their roles at any step.

🐢 Brute Force

Compute the product of every contiguous subarray directly, extending a running product one element at a time from every possible start.

func maxProductBruteForce(_ nums: [Int]) -> Int {
    var best = nums[0]

    for start in 0..<nums.count {
        var product = 1
        for end in start..<nums.count {
            product *= nums[end]
            best = max(best, product)
        }
    }

    return best
}

// smoke test
print(maxProductBruteForce([2, 3, -2, 4]))    // 6
print(maxProductBruteForce([-2, 0, -1]))      // 0
print(maxProductBruteForce([-2, 3, -4]))      // 24

Big-O: O(n^2) time — O(n) possible start points, each extending its running product over up to O(n) further elements. O(1) extra space beyond the loop variables.

🚀 Optimal

Track both a running max and running min product ending at each position; whenever the current number is negative, swap them first (since multiplying by a negative flips which one would extend to the bigger result).

func maxProduct(_ nums: [Int]) -> Int {
    var maxProd = nums[0]   // max product of a subarray ending at the current index
    var minProd = nums[0]   // min product of a subarray ending at the current index
    var result = nums[0]

    for i in 1..<nums.count {
        let num = nums[i]

        if num < 0 {
            swap(&maxProd, &minProd)   // a negative multiplier flips which extreme becomes the max
        }

        maxProd = max(num, maxProd * num)
        minProd = min(num, minProd * num)
        result = max(result, maxProd)
    }

    return result
}

// smoke test — same cases as the brute force
print(maxProduct([2, 3, -2, 4]))    // 6
print(maxProduct([-2, 0, -1]))      // 0
print(maxProduct([-2, 3, -4]))      // 24

Big-O: O(n) time — one forward pass, O(1) work per element. O(1) extra space — three rolling variables, no extra array.

🔑 The Key Insight

The brute force computes every subarray's product completely independently, redoing multiplication work that overlapping subarrays share. The optimal version tabulates forward instead, but with a twist that House Robber-style DP doesn't need: because a negative number can turn the smallest running product into the largest one (two negatives make a positive), the recurrence has to carry both a running max and a running min ending at each position, swapping them the moment a negative number is encountered. That swap is the entire extra insight over ordinary 1-D DP — everything else is the same "extend or restart" logic as Maximum Subarray Sum, just doubled up to track both extremes instead of one.

🔗 Related Chapters

  • 1D Dynamic Programming — a single forward sweep where each position's answer depends only on the previous position's tracked values, the same shape as chapter 26's rolling recurrences — extended here to two tracked values instead of one.
  • Arrays and Strings — the whole optimal solution is one left-to-right pass over nums, updating rolling variables in place.

🧸 Memory Sentence

Maximum Product Subarray is Maximum Subarray Sum with a landmine — track both the running max and running min ending at each position, and swap them the instant a negative number threatens to flip which one matters.

✅ Check Your Understanding

  1. For [-2, 3, -4], trace maxProd, minProd, and result after each iteration. At which index does the swap happen, and why does the final answer of 24 require that swap to have occurred?
  2. Why does encountering a 0 in the array effectively "reset" both maxProd and minProd to 0 at that position (check the max(num, maxProd * num) / min(num, minProd * num) lines with num = 0)?
  3. Why is a running min needed here at all, when Maximum Subarray Sum (an addition-based version of this problem) only ever needs a running max?

⬅️ Previous: Coin Change · Next: Word Break ➡️

Clone this wiki locally