maximum-product-subarray

Difficulty: Medium  ·  Topic: 1-D Dynamic Programming  ·  Practice it on parikshan: /practice/maximum-product-subarray/start

The story

An Airbnb pricing experiment logs a multiplicative adjustment per night: 1.10 means "raise 10%", 0.90 means "lower 10%", and (rarely, after a refund or correction) a value like -1.1 represents a directional flip in the model's recommendation. The analytics team wants the contiguous window of nights during which the running compound multiplier was largest. That window is the strongest single experiment phase to write up.

That window is maximum-product-subarray. The same arithmetic structure appears in compounded returns on a hedge fund's strategy, gain factors along a signal-processing chain, accumulated probabilities along a hidden Markov path before a normalisation step, and biological dose-response chains where each step multiplies (not adds) the prior signal.

This problem is also the most common DP brain-teaser in interviews because the obvious adaptation of Kadane (track one scalar, the running max product) silently breaks on negatives.

What's actually being asked

Given an integer array nums of length n, find a contiguous non-empty subarray with the largest product and return that product.

Examples:

• nums = [2, 3, -2, 4] → 6. The window [2, 3] gives 6. Including the -2 drops the running product to -12; including 4 makes it -48. Stopping early wins.
• nums = [-2, 0, -1] → 0. The single [0] matches; the products of the negatives are -2 and -1.
• nums = [-3] → -3.
• nums = [-2, 3, -4] → 24. Take the whole array: -2 * 3 * -4 = 24. Two negatives multiplied are positive: the most dangerous case for naive Kadane.

The naive approach

For each (i, j), multiply nums[i..j]. O(n²) or O(n³) depending on rebuilding. At n = 10⁵ you're past the time limit by orders of magnitude.

The key insight

For sums, "best so far" is one number, because adding a fresh negative to a running sum monotonically decreases it. For products, multiplying by a negative number flips sign: a very small (very negative) running product can become very large (very positive) on the next negative. The recurrence must therefore remember both the largest and the smallest running product up to here:

# Dual-state recurrence:
# cur_max[i] = max product of any subarray ending at index i
# cur_min[i] = min product of any subarray ending at index i
#
# cur_max[i] = max( nums[i] , cur_max[i-1] * nums[i] , cur_min[i-1] * nums[i] )
# cur_min[i] = min( nums[i] , cur_min[i-1] * nums[i] , cur_max[i-1] * nums[i] )
#
# Base: cur_max[0] = cur_min[0] = nums[0]
# Answer = max over i of cur_max[i]

A neat algebraic shortcut: when nums[i] < 0, swap cur_max and cur_min before the update. That collapses the three-way max/min into a two-way comparison.

The four DP questions:

1. State: a pair (cur_max, cur_min). cur_max[i] is the largest product of any subarray ending at i; cur_min[i] is the smallest.
2. Base case: cur_max = cur_min = nums[0].
3. Transition: candidates for the new cur_max are nums[i], cur_max * nums[i], cur_min * nums[i]. Same three candidates feed the new cur_min.
4. Answer: running maximum of cur_max across the scan.

The lesson (and it is the single most common DP brain-teaser in the cluster) is that the state size depends on the operation. Addition needs one scalar; multiplication needs two because of sign.

Step-by-step approach

The compact swap-on-negative form:

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

Or, the explicit three-way form (slightly slower but stares straight at the recurrence):

def max_product(nums):
    cur_max = cur_min = best = nums[0]
    for x in nums[1:]:
        a, b = cur_max * x, cur_min * x
        cur_max = max(x, a, b)
        cur_min = min(x, a, b)
        if cur_max > best:
            best = cur_max
    return best

Both are O(n) time, O(1) space.

Worked example

nums = [2, 3, -2, 4]

Return 6. Verified.

Now the dangerous case nums = [-2, 3, -4]:

Return 24. Verified. Without cur_min, we would have computed max(3 * -4, -4) = -4 and reported 3. Wrong.

Complexity

• Time: O(n) single pass.
• Space: O(1) with three scalars.

Common pitfalls

• Single-scalar Kadane adaptation: writing cur = max(x, cur * x) and ignoring cur_min. This is the canonical bug; it fails on any input with two negatives in a row that should combine.
• Resetting on zero incorrectly: when x = 0, both cur_max and cur_min become max(0, 0) and min(0, 0), which is 0. The very next non-zero element forces cur_max = x (because 0 * x = 0 < x if positive). The recurrence handles zeros automatically; do not write special cases.
• Forgetting to update best after the swap: the swap on negative is a state mutation, not the output; you still need to read cur_max afterwards and compare to best.
• Initialising best = 0: fails on all-negative arrays. Initialise best = nums[0].
• 64-bit overflow in languages with bounded integers: with nums[i] up to 10 and n up to 10⁵, products can be astronomical. Python handles big integers natively. In Go or Java use int64 carefully; in C use long long and consider overflow.

Where this shows up in the enterprise

• Airbnb pricing experiments: contiguous compounded price-multiplier window with the highest cumulative gain.
• Uber surge analysis: surge multipliers chained together; find the strongest contiguous surge episode.
• Hedge fund return analysis (Bloomberg analytics, Two Sigma): contiguous compounded daily-return window with the highest realised gain. Signed factors (occasional negative shocks) make this the canonical real-world example.
• Hidden Markov path scoring in speech recognition (Apple Siri, Google Assistant): before the Viterbi normalisation, products of transition probabilities form a compounded score; finding the high-score contiguous chunk of an utterance maps to this DP.
• Genomics signal chains (Illumina basecalling, Oxford Nanopore squiggle analysis): per-base confidence multipliers compound along a strand; the strongest run is the candidate read.
• Compounded A/B test gains at Stripe and Shopify: each minor variant multiplies a conversion lift; find the contiguous block of variants with the strongest cumulative effect.

The brain-teaser status of this problem is earned: when a chain of multiplicative factors can include sign flips, always track both extremes.

Variants you'll see elsewhere

• maximum-subarray: the additive twin; one scalar suffices.
• subarray-product-less-than-k: count subarrays whose product is below a threshold; sliding window plus running product (all positive simplifies things).
• maximum-product-of-three-numbers: not subarray, just product of three from the whole array; sorting twist (pick the two smallest negatives if their product exceeds the second and third largest positives).
• subarrays-with-product-divisible-by-k and other product-modulus variants: same dual-state idea generalises when the operation has non-monotone behaviour.

How parikshan turns this into a learning loop

This problem is the gateway from "one-scalar 1-D DP" (climbing-stairs, max-subarray, house-robber) to "small-state 1-D DP" where the state has a constant size larger than one.

1. Read this article. The dual-state recurrence is the entire lesson.
2. Practice mode with no AI: write Kadane (one-scalar) on nums = [-2, 3, -4] first. Watch it return 3 instead of 24. Now you have felt the bug. Write the dual-state version.
3. AI training: Explain the difference between max-subarray and max-product-subarray. The assistant should say "products flip sign on negatives, so you need both the running max and the running min". If it does not mention sign flipping, do not trust the rest of its DP explanations.
4. AI training: Find Bugs. Submit single-scalar Kadane to the assistant and ask why it fails on [-2, 3, -4]. The explanation is the whole article.
5. Exam mode: redo cold. The bank's adversarial test includes inputs designed to trigger the sign-flip bug: [-1, -2, -3], [2, -5, -2, -4, 3], and zero-laden cases. If you wrote the dual-state version correctly, all of them pass.

In the AI-integrated workspace

This is the highest-leverage interview question for spotting AI failures, because the wrong answer compiles and almost works.

• The single-scalar trap: agents asked for "max product subarray" often produce single-scalar Kadane variants and ship code that is wrong on every input with two-negative interactions. Sample-test passes; production breaks.
• The "abs trick" trap: agents sometimes propose "take abs of everything, run max-subarray, then check sign". This is meaningless; the absolute-value array has no relationship with the original problem's optimum.
• The brute-force trap: faced with the subtlety, agents fall back to O(n²) "try every subarray and compute the product". Sample-test passes; stress test on n=10⁵ times out.

The 2027 engineer's discipline:

1. Recognise the problem class. "Multiplicative running aggregate with potential sign flips" requires dual state. Always.
2. State the recurrence in English. "Track both cur_max and cur_min. On each element, the new max is max(element, prev_max * element, prev_min * element). Symmetrically for min."
3. Verify on [-2, 3, -4]. The answer must be 24. If an agent's code returns 3, the agent ran single-scalar Kadane; reject the code.
4. Verify on [0] and [0, 2]. Zeros are a corner case the dual-state recurrence handles cleanly without special-casing; if the agent special-cases zero, the recurrence is unstable in its head.
5. Run the dual-state proof in your head: at each step, the new max is the largest among three terms; the new min is the smallest among the same three. That is the entire algorithm, in two lines.

The discipline to call out "we need both max and min because of sign" is exactly the kind of seven-second insight that distinguishes engineers who direct AI from engineers who approve AI's plausible-looking errors.