Generated by Codex with GPT-5

Quick facts

• Difficulty: MEDIUM
• Problem: Maximum Product Subarray
• Main tags: Array, Dynamic Programming

What the problem is really asking

This problem asks for the contiguous subarray whose product is as large as possible.

That sounds close to Maximum Subarray, but products behave very differently from sums. With sums, a very negative running total is usually bad news. With products, a very negative running product can suddenly become the best thing to keep if the next number is also negative.

That is the whole difficulty of the problem:

• positive numbers keep the sign the same
• negative numbers flip the sign
• zero breaks any running product and forces a restart

So the real question is not just “what is the best product so far?” It is:

“What are the best and worst products of any subarray that must end at this index?”

The worst one matters because it might become the best one after multiplying by a negative number.

Why a single running maximum is not enough

If this were the sum version, the usual Kadane-style idea would be:

• either start a new subarray here
• or extend the previous best subarray

That logic breaks for products.

Take [-2, 3, -4].

At index 1, the best product ending there is 3, but the most useful state is also -6, because multiplying -6 by -4 gives 24, which is the final answer. If an algorithm only remembers the current maximum product, it throws away exactly the state that later becomes optimal.

That is why the correct dynamic programming state must track two values at every step:

• the largest product ending here
• the smallest product ending here

The key insight: each position has three candidates

Suppose the current number is value, and the previous position already knows:

• previous_max_ending_here
• previous_min_ending_here

Then any subarray ending at the current position must be one of these three things:

1. start fresh with just value
2. extend the previous maximum product subarray with value
3. extend the previous minimum product subarray with value

So the transition is:

• new_max = max(value, value * previous_max, value * previous_min)
• new_min = min(value, value * previous_max, value * previous_min)

This works because multiplying by a negative number swaps the roles of “good” and “bad.” A previously tiny negative product can become the new maximum, and a previously large positive product can become the new minimum.

Zero is handled naturally. When value = 0, both the new maximum and new minimum become 0, which effectively resets the running product for the next position.

A concrete example

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

At -2:

• max ending here = -2
• min ending here = -2
• best overall = -2

At 3, the three candidates are:

• 3
• 3 * -2 = -6
• 3 * -2 = -6

So:

• max ending here = 3
• min ending here = -6
• best overall = 3

At -4, the three candidates are:

• -4
• -4 * 3 = -12
• -4 * -6 = 24

So:

• max ending here = 24
• min ending here = -12
• best overall = 24

That last step is the key pattern to remember: the new answer came from the previous minimum, not the previous maximum.

How to derive this in an interview

A strong interview derivation is:

1. Start with the brute-force version that checks every subarray in O(n^2).
2. Ask what information from the previous index is actually needed to extend a subarray ending here.
3. Notice that because negatives flip signs, the previous maximum alone is not enough.
4. Introduce the paired state: maximum product ending here and minimum product ending here.
5. Show the three-candidate transition and explain why it covers every possible subarray ending at the current index.

That is usually enough to move from brute force to the optimal O(n) dynamic programming solution in a way that sounds reasoned rather than memorized.

Python solution

from typing import List, Tuple


def update_product_extremes(
    value: int,
    previous_max_ending_here: int,
    previous_min_ending_here: int,
) -> Tuple[int, int]:
    """
    Return the largest and smallest products of a subarray that must end at
    the current value.
    """
    candidate_products = (
        value,
        value * previous_max_ending_here,
        value * previous_min_ending_here,
    )
    return max(candidate_products), min(candidate_products)


def maximum_product_subarray(values: List[int]) -> int:
    """
    Return the largest product over all contiguous subarrays.

    The algorithm tracks both the best and worst products ending at each
    position because a negative number can swap their roles.
    """
    if not values:
        raise ValueError("values must contain at least one integer")

    max_ending_here = values[0]
    min_ending_here = values[0]
    best_product_seen = values[0]

    for value in values[1:]:
        max_ending_here, min_ending_here = update_product_extremes(
            value=value,
            previous_max_ending_here=max_ending_here,
            previous_min_ending_here=min_ending_here,
        )

        if max_ending_here > best_product_seen:
            best_product_seen = max_ending_here

    return best_product_seen


class Solution:
    def maxProduct(self, nums: List[int]) -> int:
        return maximum_product_subarray(nums)

Why this works

After processing index i, max_ending_here is the largest product of any contiguous subarray that ends exactly at i, and min_ending_here is the smallest product of any contiguous subarray that ends exactly at i.

That invariant is true at the first element by direct initialization. For each later element, every valid subarray ending at i either starts at i itself or extends some subarray ending at i - 1. Among those previous subarrays, only the maximum and minimum products matter, because any other product lies between them and cannot produce a more extreme result after multiplying by the current value. The transition therefore checks every relevant possibility.

Since best_product_seen records the largest max_ending_here over the whole scan, the algorithm returns the best product among all contiguous subarrays.

The runtime is O(n) because each element is processed once. The extra space is O(1) because the algorithm keeps only a few scalar variables.

Interview follow-ups

Can you also return the start and end indices of the best subarray?

Yes, but the bookkeeping becomes a little more detailed. Along with max_ending_here and min_ending_here, the algorithm should track where each of those subarrays started. When a new extreme comes from value alone, the start index becomes the current index. When it comes from extending a previous extreme, the start index is inherited from that previous state. Whenever best_product_seen improves, the algorithm records the current end index together with the start index of max_ending_here. The complexity stays O(n) time and O(1) extra space, but the implementation becomes more careful because the value updates and index updates must stay aligned.

Why do zeroes not need a separate reset branch?

They are already handled by the same recurrence. If value is 0, then the candidate products are 0, 0 * previous_max, and 0 * previous_min, so both new extremes become 0. That naturally ends every product chain that reaches this index. On the next element, the recurrence again decides whether it is better to start fresh or extend from zero. This is a good example of why the three-candidate transition is elegant: it handles positive numbers, negative numbers, and zero with one consistent rule instead of special-case logic scattered through the loop.

Is there another optimal O(n) approach?

Yes. A common alternative is to scan left to right and right to left, maintaining a running product and resetting it after zeroes. That works because when zero is absent, the best product subarray can be found by dropping either the prefix up to the first negative or the suffix after the last negative whenever the total count of negatives is odd. The bidirectional scan captures that idea in O(n) time and O(1) space. It is a valid interview answer, but the max/min dynamic programming version is usually easier to justify on the spot because it works through a direct local recurrence and makes the negative-number behavior explicit.

Why is this considered dynamic programming instead of just a greedy scan?

Because each step reuses a precisely defined optimal substructure from the previous step. The state is small, but it is still stateful recurrence-based reasoning: the best and worst products ending at index i are computed from the corresponding extremes at index i - 1. A greedy algorithm would usually make an irreversible local choice without preserving all the state needed later. Here, the algorithm intentionally keeps both extremes because either one may become important at the next negative number. That retention of multiple necessary subproblem results is what makes the solution dynamic programming.

Practical takeaway

The fastest way to remember this problem is:

do not track only the best running product.

Track the best and worst products ending at each position, because the next negative number may swap them. Once that idea clicks, the whole solution becomes a short O(n) scan.