Maximum Product Subarray Solution

Problem

Given an array of integers, find the contiguous subarray that produces the largest product and return that product. Unlike the maximum sum subarray, a negative number can flip a tiny product into a huge one — but only if there's another negative later to flip it back.

Input: nums = [2, 3, -2, 4]
Output: 6
Explanation: The subarray [2, 3] yields the largest product; extending to -2 or 4 makes it smaller.

Counter-example: [-2, 0, -1] returns 0 — the zero breaks any subarray that might span both negatives, so the best we can do is an empty product of 0.

Intuition

The key difference from maximum sum subarray is that negatives can be redeemed: -6 × -4 = 24, so a deeply negative running product can suddenly become the largest if we hit another negative. This means tracking only the running maximum is not enough — we must also track the running minimum, because the minimum (most negative) product can flip into the new maximum the moment we multiply by a negative number.

Approach 1 — Brute Force

Try every possible subarray by iterating over all start positions, then extending to each end position and accumulating the product.

Initialize max_product to nums[0] (not 0 — the array can be all negative).
For each starting index, reset the running product to 1.
For each ending index from the start onward, multiply in the current element.
Update max_product if the running product is larger.
Return max_product.

1def maxProduct(nums):
2    max_product = nums[0]
3    for start in range(len(nums)):
4        running_product = 1
5        for end in range(start, len(nums)):
6            running_product *= nums[end]
7            max_product = max(max_product, running_product)
8    return max_product

Time: O(n²) — two nested loops over all subarray boundaries.
Space: O(1) — only a handful of variables.

Approach 2 — Track Max and Min Simultaneously

At each position the best subarray ending here is one of three things: the element alone (start fresh), the element times the previous maximum, or the element times the previous minimum (since negative × negative = positive). Track all three and pick the best.

Initialize max_product, current_max, and current_min all to nums[0].
For each subsequent element, compute three candidates: the element alone, element × current_max, element × current_min.
Capture all candidates before overwriting — both updates need the old values.
Set current_max to the largest candidate and current_min to the smallest.
Update max_product with current_max and return it at the end.

1def maxProduct(nums):
2    max_product = nums[0]
3    current_max = nums[0]
4    current_min = nums[0]
5
6    for num in nums[1:]:
7        # Compute all three candidates before overwriting anything
8        candidates = (num, current_max * num, current_min * num)
9        current_max = max(candidates)
10        current_min = min(candidates)
11        max_product = max(max_product, current_max)
12
13    return max_product

Time: O(n) — a single pass through the array.
Space: O(1) — three variables regardless of input size.

Complexity Summary

Approach	Time	Space	When to use
Brute Force	O(n²)	O(1)	Tiny inputs or when you need a simple verifier to test against
Track Max and Min	O(n)	O(1)	Always — same space cost, far faster

Common Mistakes

Updating current_max before computing current_min — both calculations need the previous values of each other. If you write currentMax = ... first in Java or C++, currentMin will silently multiply by the freshly updated currentMax, producing the wrong answer. Always snapshot or compute all candidates together first.
Only tracking the maximum, not the minimum — without current_min, you'd miss cases like [-3, -4] where the minimum running product (-3) multiplied by -4 gives the true maximum (12). The entire trick of this problem lives in that second variable.
Assuming zeros are a special case to handle separately — they're not. The "element alone" candidate naturally handles zeros: max(0, prev_max × 0, prev_min × 0) = 0, so both trackers reset to 0 after a zero, which is exactly right.
Initializing max_product to 0 — the input can be entirely negative, making the answer the least-negative single element (e.g., [-3, -5, -2] → -2). Initializing to 0 would incorrectly return 0 for inputs with no non-negative elements.
Confusing this with maximum sum subarray — Kadane's algorithm for sums resets to the current element whenever the running sum goes negative. Copying that logic here and discarding a negative product is wrong: the product could be redeemed by a later negative, which the current_min tracker exists to capture.

Maximum Product Subarray — Solution