Maximum Product Subarray: Algorithm, Code, and Dry Run

Given an integer array, the maximum product subarray is the contiguous subarray whose product of elements is the largest.

Negative numbers and zeros are what make this harder than the maximum sum version. A negative element can flip the sign of a running product, turning the current worst into the new best. Zeros reset everything. The O(n) solution tracks two running values at every index to handle both.

The Problem and Why Negatives Make It Hard

Formally: find contiguous indices i through j such that arr[i] × arr[i+1] × ... × arr[j] is maximised.

The example carried through this article:

• Input: {-1, -3, -10, 60, 0}
• Correct output: 1800
• Winning subarray: {-3, -10, 60}
• Verification: -3 × -10 = 30, then 30 × 60 = 1800

Compare this to maximum sum subarray. In the sum version, a negative element only ever hurts the running total, so discarding it is always safe. In the product version, two negatives multiply to a positive. The subarray {-3, -10, 60} wins because the two negatives cancel before the large positive multiplier. Any algorithm that treats negatives as unconditional discards will miss results like this.

Why a Greedy Approach Fails

An intuitive but incorrect strategy is to skip every negative element and multiply only the positives. Applied to the five-element example, this strategy keeps only 60, giving a product of 60 instead of 1800.

A cleaner three-element counterexample:

• Input: {-2, 3, -4}
• Greedy (skip negatives): keeps only 3. Result: 3.
• Correct answer: -2 × 3 × -4 = 24. Winning subarray is the entire array.

The greedy discards -2 and -4, losing a factor of 8 from the result. Pairs of negatives flip sign twice, and any algorithm blind to this pairing will systematically underestimate products that include them.

The Max-Min Tracking Algorithm

At each index the algorithm maintains three values:

• max_here: the largest product of any subarray ending exactly at this index
• min_here: the smallest (most negative) product of any subarray ending here
• result: the best max_here seen so far across the entire array

For each element arr[i], three candidates compete:

1. arr[i] alone — starting a fresh subarray at this position
2. max_here * arr[i] — extending the current maximum subarray
3. min_here * arr[i] — extending the current minimum, which flips sign when arr[i] is negative

The new max_here is the maximum of all three candidates. The new min_here is the minimum of all three. Because computing min_here uses the old max_here, a temporary variable captures the new max_here before min_here is updated; updating in-place would produce wrong results on negative elements.

This approach is a variant of Kadane’s algorithm extended to track paired extremes, as covered in GeeksforGeeks’s treatment of the maximum product subarray.

Dry Run Walkthrough

Initial state for {-1, -3, -10, 60, 0}: max_here = -1, min_here = -1, result = -1.

Step	Element	el alone	max_here × el	min_here × el	New max_here	New min_here	Result
init	-1	—	—	—	-1	-1	-1
i=1	-3	-3	3	3	3	-3	3
i=2	-10	-10	-30	30	30	-30	30
i=3	60	60	1800	-1800	1800	-1800	1800
i=4	0	0	0	0	0	0	1800

At step i=2, min_here × el = (-3) × (-10) = 30 wins the max competition because the two negatives cancel. At step i=3, max_here × el = 30 × 60 = 1800 wins. The zero at i=4 collapses both running values to 0 but cannot overwrite the stored result of 1800.

For array-traversal techniques that maintain a running state across all elements, see find the equilibrium index of an array.

Python and C Implementations

Both follow the same three-candidate update logic. The Python version uses a tuple to capture all candidates before updating either running variable. The C version uses an explicit temp for the same reason.

Python

def max_product_subarray(arr):
    if not arr:
        return 0

    max_here = arr[0]
    min_here = arr[0]
    result   = arr[0]

    for i in range(1, len(arr)):
        el = arr[i]
        candidates = (el, max_here * el, min_here * el)
        max_here = max(candidates)
        min_here = min(candidates)
        result   = max(result, max_here)

    return result

# Example
arr = [-1, -3, -10, 60, 0]
print(max_product_subarray(arr))   # Output: 1800

The candidates tuple freezes the three values before either max_here or min_here changes. Calling max() and min() on the same tuple avoids the in-place corruption described in the algorithm section.

C

#include <stdio.h>

int max3(int a, int b, int c) { return a > b ? (a > c ? a : c) : (b > c ? b : c); }
int min3(int a, int b, int c) { return a < b ? (a < c ? a : c) : (b < c ? b : c); }

int maxProductSubarray(int arr[], int n) {
    int max_here = arr[0];
    int min_here = arr[0];
    int result   = arr[0];
    int temp;

    for (int i = 1; i < n; i++) {
        temp     = max3(arr[i], max_here * arr[i], min_here * arr[i]);
        min_here = min3(arr[i], max_here * arr[i], min_here * arr[i]);
        max_here = temp;
        if (max_here > result) result = max_here;
    }
    return result;
}

int main() {
    int arr[] = {-1, -3, -10, 60, 0};
    int n = 5;
    printf("Maximum product: %d\n", maxProductSubarray(arr, n));  /* 1800 */
    return 0;
}

temp is assigned before min_here is updated, so both max3 and min3 calls operate on the same old max_here. Swapping the assignment order is a common implementation mistake; both running variables must use the pre-update values.

Time and Space Complexity

The algorithm makes a single left-to-right pass:

• Time complexity: O(n). Each element is visited once; the work per element is constant (three multiplications, a comparison, and two variable updates).
• Space complexity: O(1). Only max_here, min_here, and result are maintained beyond the input array. No stack, recursion, or auxiliary structure is needed.

A brute-force approach that checks every contiguous subarray runs in O(n²) time. The gap grows with input length:

• Array of 100 elements: brute-force runs around 5,000 operations; single-pass runs 100.
• Array of 10,000 elements: brute-force runs around 50 million operations; single-pass runs 10,000.

Placement interviewers ask for the O(n) solution specifically because it demonstrates awareness of this gap. For a wider look at how single-pass algorithms achieve constant auxiliary space, see space complexity of algorithms with examples.

Where This Problem Appears in Placement Tests

The maximum product subarray is a medium-difficulty coding problem that features in placement rounds at service-tier IT companies. Two things come up consistently: the interviewer expects an O(n) implementation, and they ask the candidate to explain why the greedy skip-negatives approach produces wrong results.

Having a ready counterexample is useful. The three-element array {-2, 3, -4} isolates the failure clearly: greedy gives 3, correct answer is 24, and the reason fits in one sentence (two negatives cancel to multiply the 3 by a factor of 8).

LeetCode Problem 152 covers this problem with a time limit that approximates placement-test pacing. For related array problems that pair well with this one in interview prep, see find all symmetric pairs in an array.

The two-variable tracking pattern, max_here and min_here updating in lockstep to survive sign flips, recurs in production AI systems in a similar form: beam search and gradient clipping both maintain paired bounds at each step. TinkerLLM at ₹299 is where that kind of algorithmic thinking meets hands-on AI building.