152. Maximum Product Subarray - Explanation

Problem Link

Description

Given an integer array nums, find a subarray that has the largest product within the array and return it.

A subarray is a contiguous non-empty sequence of elements within an array.

You can assume the output will fit into a 32-bit integer.

Example 1:

Input: nums = [1,2,-3,4]

Output: 4

Example 2:

Input: nums = [-2,-1]

Output: 2

Constraints:

  • 1 <= nums.length <= 1000
  • -10 <= nums[i] <= 10


Recommended Time & Space Complexity

You should aim for a solution with O(n) time and O(1) space, where n is the size of the input array.


Hint 1

A brute force solution would be to find the product for every subarray and then return the maximum among all the products. This would be an O(n ^ 2) approach. Can you think of a better way? Maybe you should think of a dynamic programming approach.


Hint 2

Try to identify a pattern by finding the maximum product for an array with two elements and determining what values are needed when increasing the array size to three. Perhaps you only need two values when introducing a new element.


Hint 3

We maintain both the minimum and maximum product values and update them when introducing a new element by considering three cases: starting a new subarray, multiplying with the previous max product, or multiplying with the previous min product. The max product is updated to the maximum of these three, while the min product is updated to the minimum. We also track a global max product for the result. This approach is known as Kadane's algorithm.


Company Tags

Please upgrade to NeetCode Pro to view company tags.



1. Brute Force

Intuition

A subarray product can change drastically because of:

  • Negative numbers → can flip max to min and vice-versa
  • Zero → resets the product

In brute force, we:

  • Fix a starting index
  • Keep multiplying elements to the right
  • Track the maximum product seen

This works because every possible contiguous subarray is explicitly evaluated.

Algorithm

  1. Initialize res with the first element.
  2. For each starting index i:
    • Set cur = nums[i].
    • Update res.
    • For every j > i:
      • Multiply cur *= nums[j].
      • Update res.
  3. Return res.
class Solution:
    def maxProduct(self, nums: List[int]) -> int:
        res = nums[0]

        for i in range(len(nums)):
            cur = nums[i]
            res = max(res, cur)
            for j in range(i + 1, len(nums)):
                cur *= nums[j]
                res = max(res, cur)

        return res

Time & Space Complexity

  • Time complexity: O(n2)O(n ^ 2)
  • Space complexity: O(1)O(1)

2. Sliding Window

Intuition

The maximum-product subarray problem is tricky because:

  • A negative number flips the sign (a very small negative can become a very large positive after another negative).
  • A zero breaks any product (anything crossing a zero becomes 0).

So we can treat the array as separate segments split by zeros.
Inside one zero-free segment:

  • If the count of negative numbers is even, the product of the whole segment is positive → usually the best.
  • If the count is odd, we must drop either the prefix up to the first negative or the suffix after the last negative to make the remaining product have an even number of negatives.

This “sliding window” idea maintains a window that contains an allowed number of negatives (even), shrinking from the left when we exceed that.

Algorithm

  1. Initialize res as the maximum element seen so far (important for cases like all negatives or zeros).
  2. Split nums into zero-free subarrays (segments). Each zero ends a segment.
  3. For each segment:
    • Count how many negatives it has.
    • Decide how many negatives the best window should contain:
      • If negatives are even, keep all (need = negs).
      • If negatives are odd, keep one less (need = negs - 1).
    • Use two pointers j..i with a running product:
      • Extend i to the right multiplying into prod.
      • Track how many negatives are in the window.
      • If negatives exceed need, move j right, dividing out elements, until valid again.
      • Update res with prod whenever the window is valid.
  4. Return res.
class Solution:
    def maxProduct(self, nums: List[int]) -> int:
        A = []
        cur = []
        res = float('-inf')

        for num in nums:
            res = max(res, num)
            if num == 0:
                if cur:
                    A.append(cur)
                cur = []
            else:
                cur.append(num)

        if cur:
            A.append(cur)

        for sub in A:
            negs = sum(1 for i in sub if i < 0)
            prod = 1
            need = negs if negs % 2 == 0 else negs - 1
            negs = 0
            j = 0

            for i in range(len(sub)):
                prod *= sub[i]
                if sub[i] < 0:
                    negs += 1
                    while negs > need:
                        prod //= sub[j]
                        if sub[j] < 0:
                            negs -= 1
                        j += 1
                if j <= i:
                    res = max(res, prod)

        return res

Time & Space Complexity

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

3. Kadane's Algorithm

Intuition

This is the Kadane-style solution adapted for products.

In the classic maximum-sum subarray, we only track one value (current max sum).
For products, that’s not enough because:

  • A negative × negative = positive
  • A very small (negative) product can suddenly become the maximum after multiplying by another negative.

So at every index, we must track two values:

  • curMax: maximum product ending at this index.
  • curMin: minimum product ending at this index.

Why curMin matters:

  • If the current number is negative, multiplying it with curMin might produce a new maximum.

Zeros are naturally handled because choosing num alone can reset the product.

Algorithm

  1. Initialize:
    • res = first element (answer so far).
    • curMax = 1, curMin = 1.
  2. For each number num in the array:
    • Temporarily store curMax * num (because curMax will be updated).
    • Update curMax as the maximum of:
      • num (start new subarray).
      • num * curMax (extend previous max).
      • num * curMin (negative flip case).
    • Update curMin as the minimum of:
      • num.
      • previous curMax * num.
      • num * curMin.
    • Update res = max(res, curMax).
  3. Return res.
class Solution:
    def maxProduct(self, nums: List[int]) -> int:
        res = nums[0]
        curMin, curMax = 1, 1

        for num in nums:
            tmp = curMax * num
            curMax = max(num * curMax, num * curMin, num)
            curMin = min(tmp, num * curMin, num)
            res = max(res, curMax)
        return res

Time & Space Complexity

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

4. Prefix & Suffix

Intuition

The key idea is that the maximum product subarray must appear as either:

  • a prefix product of some segment, or
  • a suffix product of some segment.

Why this works:

  • Negative numbers flip signs. If a subarray has an even number of negatives, the full product is positive.
  • If it has an odd number of negatives, removing either:
    • the prefix up to the first negative, or
    • the suffix after the last negative
      will give the maximum product.
  • Zeros break subarrays completely, so products must restart after a zero.

By scanning:

  • once from left to right (prefix)
  • once from right to left (suffix)

we implicitly consider all valid subarrays without explicitly tracking negatives.

The (prefix or 1) trick resets the product after encountering 0.

Algorithm

  1. Initialize:
    • res as the first element.
    • prefix = 0, suffix = 0.
  2. For i from 0 to n - 1:
    • Update prefix product:
      • prefix = nums[i] * (prefix if prefix != 0 else 1).
    • Update suffix product:
      • suffix = nums[n - 1 - i] * (suffix if suffix != 0 else 1).
    • Update result:
      • res = max(res, prefix, suffix).
  3. Return res.
class Solution:
    def maxProduct(self, nums: List[int]) -> int:
        n, res = len(nums), nums[0]
        prefix = suffix = 0

        for i in range(n):
            prefix = nums[i] * (prefix or 1)
            suffix = nums[n - 1 - i] * (suffix or 1)
            res = max(res, max(prefix, suffix))
        return res

Time & Space Complexity

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

Common Pitfalls

Ignoring Negative Numbers Can Become Positive

Unlike maximum sum subarray, a very negative product can become the maximum after multiplying by another negative number. Tracking only the current maximum is insufficient. You must track both curMax and curMin because multiplying curMin by a negative number might produce the new maximum.

Forgetting to Handle Zeros

A zero in the array resets the product to zero and effectively splits the array. After encountering a zero, the subarray must restart fresh. Failing to handle this case causes the algorithm to carry forward zero products incorrectly.

Not Saving the Previous Maximum Before Updating

When computing the new curMax and curMin, the calculation for curMin may depend on the old value of curMax. Updating curMax first and then using the new value to compute curMin produces wrong results. Always store curMax * num in a temporary variable before updating either value.