What is the brute force approach and complexity for Maximum Product Subarray?

Multiply each start's numbers one by one; track the largest product with time complexity O(N^2) and space complexity O(1).

What is the optimal approach and complexity for Maximum Product Subarray?

Keep the largest and smallest product of blocks ending here; a negative number swaps their roles with optimal time complexity O(N) and space complexity O(1).

How do you identify the pattern for Maximum Product Subarray?

Look for key signals in the prompt: "contiguous block" indicates The answer is a range [l … r], so we walk left to right and keep a running state that ends at each index.; "largest product" indicates Multiplying a longer block does not always help, so one running value is not enough.; "numbers can be negative" indicates A negative number flips the sign, so the smallest product can become the largest. We must track both..

Maximum Product Subarray

Medium·LeetCode #152Basic Anchor

LeetCode

Jump:

30-Second Mental ModelKadane with two states: max product and min product (Maximum product)

Complexity:O(N^2)→O(N)

Key Insight

Walk left to right and keep two values: curMax, the biggest product of a block that ends at the current index, and curMin, the smallest. A block ending here is either the new number alone or an earlier block times the new number, so the biggest comes from x, x · curMax, or x · curMin. We keep the smallest too, because a negative x turns the smallest product into the biggest.

Core Validity Invariant

The two extremes are enough: the biggest and smallest products ending at i − 1 decide the biggest and smallest products ending at i.

Problem

You are given an integer array nums. Look at every contiguous block: a run of numbers that sit next to each other with nothing skipped. The product of a block is all its numbers multiplied together.

Return the largest product that any non-empty block has.

Input

An integer array nums of length n.

Output

A single integer: the largest product of any non-empty contiguous block.

Example 1

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

Output: 6

The block [2, 3] gives 6. Adding the -2 makes the product negative: the whole array gives -48, so 6 is the best.

Example 2

Input: nums = [-2, 0, -1]

Output: 0

Any block that contains the 0 has product 0. The single blocks [-2] and [-1] are negative, so the best is 0.

Constraints

• 1 ≤ nums.length ≤ 2 × 10^4
• −10 ≤ nums[i] ≤ 10
• The product of any contiguous block fits in a 32-bit integer.

First, think yourself

Before opening any solution, try to answer these on paper. Use hints only when stuck — each hint is counted.

1.
For the maximum sum of a block, I kept only the best sum that ends here. Why might that break when I multiply instead of add?
2.
If the best product ending at the previous index is very negative, what happens after I multiply it by another negative number?
3.
What does a 0 do to every block that contains it?
4.
How many blocks end at index i, and can I reuse what I already found for index i − 1?
5.
Is there any other block ending at i − 1 that could still matter after the next multiply?

Brute force approach

Idea

A block is decided by where it starts and where it ends. For each start, multiply the numbers one at a time going right, and keep the largest product seen. That covers every block, so the answer is correct, but there are about n²/2 blocks to check.

Thinking process

1
The answer is one block, so I need to check every block: every start, and every end after it.
2
For start 0 of [2, 3, -2, 4] the products are 2, 6, -12, -48. Each one is the previous product times the next number, so nothing is multiplied twice.
3
Start 1 gives 3, -6, -24. Start 2 gives -2, -8. Start 3 gives 4. The largest of all these is 6.
4
Keep the running product in a long long. The problem says each block's product fits in 32 bits, so the final cast back to int is safe.

Visual

Every block is checked once: 28 blocks for 7 numbers. The count grows with n², so it is too slow for large inputs.

Brute force checks every blocknums = [2, 3, -2, -4, 0, -1, 5]step 1/28

nums

-2

-4

-1

▲L R

Work

block: [2]
product: 2
best: 2
blocks checked: 1 / 28

Block 1 of 28

Block [0..0] has product 2. Best so far: 2.

Code & Implementation

brute.cpp

class Solution {
public:
    int maxProduct(vector<int>& nums) {
        int n = nums.size();
        long long best = LLONG_MIN;

        // Every block starts at some index. Grow each one to the right.
        for (int start = 0; start < n; start++) {
            // long long gives room while multiplying. The problem promises
            // every block's product fits in 32 bits, so the final cast is safe.
            long long product = 1;
            for (int end = start; end < n; end++) {
                product *= nums[end];
                best = max(best, product);
            }
        }
        return (int)best;
    }
};

Complexity

Time O(N^2)Space O(1)

There are n(n + 1) / 2 blocks, and each one costs one multiplication, so the work grows with n². With n = 2 × 10^4 that is about 2 × 10^8 multiplications.

Optimized approach

Idea

Start from brute force

Brute force multiplies from each start to each end: about n²/2 products, and each one is built from the product before it.

Find the repeated work

Many blocks end at the same index, and each one is an earlier block times x. Only the biggest and smallest of those earlier products can produce the biggest product now, so the others can be thrown away.

Define the state — what variables do I need?

curMax: The largest product of a block that ends at the current index.
curMin: The smallest product of a block that ends at the current index. It is kept because a negative x can turn it into the biggest.
best: The largest curMax seen so far. This is the answer at the end.

Define validity

The two extremes are enough: the biggest and smallest products ending at i − 1 decide the biggest and smallest products ending at i.

Define the transitions — when does each pointer move, and why is it safe?

Before the loop

curMax = curMin = best = nums[0]

The only block that ends at index 0 is nums[0] itself.

Every index i from 1 to n − 1

a = x · curMax; b = x · curMin; curMax = max(x, a, b); curMin = min(x, a, b)

A block ending here is either x alone or an earlier block extended by x. Both products use the old values, so compute a and b before overwriting either one.

After each update

best = max(best, curMax)

curMax is the biggest product of a block ending at i. The answer is the biggest of these over all i.

What does the current window add to the answer?

After each number, curMax is the best block that ends here. Taking the max over all indices covers every block.

Code & Implementation

optimal.cpp

class Solution {
public:
    int maxProduct(vector<int>& nums) {
        int n = nums.size();

        // curMax / curMin: largest and smallest product of a block ending at the current index.
        long long curMax = nums[0];
        long long curMin = nums[0];
        long long best = nums[0];

        for (int i = 1; i < n; i++) {
            long long x = nums[i];
            // Both candidates must use the OLD curMax and curMin, so compute them first.
            long long a = x * curMax;
            long long b = x * curMin;
            curMax = max(x, max(a, b));
            curMin = min(x, min(a, b));
            best = max(best, curMax);
        }
        return (int)best;
    }
};

Complexity

Time O(N)Space O(1)

One pass with a fixed number of variables. Each number is used once, so the work is linear.

Why does this algorithm work?

Dry run

All approaches compared

Approach	Idea	Time	Space
Brute Force	Multiply each start's numbers one by one; track the largest product	O(N^2)	O(1)
Optimal	Keep the largest and smallest product of blocks ending here; a negative number swaps their roles	O(N)	O(1)

Why does this belong to this pattern?

Clues in the problem statement

“contiguous block”The answer is a range [l … r], so we walk left to right and keep a running state that ends at each index.
“largest product”Multiplying a longer block does not always help, so one running value is not enough.
“numbers can be negative”A negative number flips the sign, so the smallest product can become the largest. We must track both.

Contiguous range ending at i+product, not sum+track max AND min because of negatives→Kadane with two states: max product and min product (Maximum product)

This is Kadane's idea with a second state. Plain Kadane keeps only the best sum ending here, which is safe for sums because adding never reverses the order. Multiplying by a negative number does reverse it, so the smallest product must be kept as well. The next question, Maximum Length with Positive Product, walks the same way but keeps lengths instead of product values.

Don't make this mistake

Pattern confusion: plain Kadane with products

✗ cur = max(x, cur * x); // only the largest product is tracked

✓ a = x * curMax; b = x * curMin; curMax = max(x, max(a, b)); curMin = min(x, min(a, b));

On the dry run [2, 3, -2, -4, 0, -1, 5] the largest-only version keeps 6 after the 3. Then -2 replaces it with -2, which throws away the -12. At -4 it gets max(-4, -4 · -2) = 8, and the program returns 8. The true answer is 48, from 2 · 3 · (-2) · (-4), and it needs the -12.

Updating curMax before computing curMin

✗ curMax = max(x, x * curMax, x * curMin); curMin = min(x, x * curMax, x * curMin);

✓ long long a = x * curMax, b = x * curMin; curMax = max(x, max(a, b)); curMin = min(x, min(a, b));

On the same dry run, after -2 the new curMax is -2. Then curMin = min(-2, -2 · -2, -2 · 3) = -6 instead of -12. At -4 the code returns max(-4, 8, 24) = 24, not 48. Both values must come from the old state.

Starting curMax at 0

✗ long long curMax = 0, curMin = 0, best = 0;

✓ long long curMax = nums[0], curMin = nums[0], best = nums[0];

With curMax = 0, a negative first number gives max(x, 0) = 0. For nums = [-3] the program returns 0 instead of -3, because the answer must be a real block.

Dropping the single number x

✗ curMax = max(x * curMax, x * curMin);

✓ curMax = max(x, max(x * curMax, x * curMin));

A block can start fresh at x. For nums = [0, 2], both values are 0 after the zero, so without x alone the 2 is never considered and the program returns 0 instead of 2.

Want to implement this?

Write it yourself on LeetCode, then come back and compare your code with the solutions above.

Open coding workspace

How did it go?

Beyond The LeetCode Problem

How this concept connects to System Design & C++ Systems

Bridge DSA with production engineering

Top engineering interviews test whether you understand how algorithms like DP — Kadane / Subarray translate into production architectures and low-level memory mechanics.

LLD Architecture