Start learning free

LESSON 446 OF 535 · DYNAMIC PROGRAMMING

Maximum Product Subarray in C++: O(n) Time with Running Max and Min

Practice O(n) Read the full explanation

Given a vector of integers nums, find the subarray with the largest product and return that product.

A subarray is a run of one or more elements that stand next to each other in nums. Its product is all of its elements multiplied together.

Example 1:

Input: nums = [2, 3, -2, 4]
Output: 6
Explanation: The subarray [2, 3] has the largest product, 2 × 3 = 6. -2 is the only negative number, so every subarray that includes it has a negative product.

Example 2:

Input: nums = [-2, 0, -1]
Output: 0
Explanation: The answer can't be 2: [-2, -1] is not a subarray, because 0 stands between them. The subarray [0] gives 0, and every other subarray gives 0 or less.

Example 3:

Input: nums = [-2, 3, -4]
Output: 24
Explanation: The whole array: the two negative numbers cancel out, -2 × 3 × -4 = 24.

Constraints:

1 <= nums.size() <= 10⁵
-10 <= nums[i] <= 10
The product of any subarray of nums fits in a 32-bit integer.

Note:

Your algorithm should run in O(n) time and use O(1) extra space, where n is the length of nums.

STEP 1 OF 9

Guided

Ctrl + Enter to check

C++ · DYNAMIC PROGRAMMING

Maximum Product Subarray in C++, explained

Problem overview

The method maxProduct receives a vector of integers nums and returns the largest product of a subarray: a run of one or more elements that stand next to each other. The product of a subarray is all of its elements multiplied together.

For nums = [2, 3, -2, 4] the answer is 6, from the subarray [2, 3]. The only negative number is -2, so every subarray that includes it has a negative product. For nums = [-2, 0, -1] the answer is 0. The product 2 of -2 and -1 is not available, because they are not next to each other: the 0 stands between them, and the subarray [0] gives 0. For nums = [-2, 3, -4] the answer is 24, the whole array, where the two negatives cancel out.

Approach: keep the best and the worst product ending here

For a sum, the best subarray ending at position i either starts fresh at i or extends the best one ending at i - 1. A product behaves differently because of signs. A very negative product can become a very positive one after one more negative factor, and a 0 resets everything.

So the pass keeps two numbers for the subarrays that end at the current element:

maxHere, the largest product of a subarray ending here;
minHere, the smallest product, which is the most negative one.

When the next element is negative, multiplying flips the order: the most negative product becomes the largest candidate, and the largest becomes the smallest. The code swaps the two before multiplying, so each is the right one to multiply by the new element. For each element there are two choices: start a new subarray at it, which is the element alone, or extend the previous one. That is how a product gets past a 0: starting fresh at the next element ignores everything before the zero.

A running result keeps the largest maxHere seen. The best subarray ends somewhere, so checking the best one ending at each element finds it. Trying every subarray by brute force would take O(n²) time, which is too slow for 100,000 elements. The one-pass method takes O(n) time and O(1) extra space.

Here is the pass on nums = [2, 3, -2, 4], as the code runs it. Each line shows the values after the element at index i is processed. The starting values at index 0 are 2 for all three variables:

i=1 nums[i]=3 maxHere=6 minHere=3 result=6
i=2 nums[i]=-2 maxHere=-2 minHere=-12 result=6
i=3 nums[i]=4 maxHere=4 minHere=-48 result=6

The product 6 is found at i = 1 and stays the answer. At i = 2, the swap exchanges 6 and 3 before multiplying by -2, which gives -12 as the smallest. And on [-2, 3, -4]:

i=1 nums[i]=3 maxHere=3 minHere=-6 result=3
i=2 nums[i]=-4 maxHere=24 minHere=-12 result=24

At i = 2, the swap makes maxHere the old smallest, -6. Multiplied by -4 it becomes 24, the best product.

Step by step

Create maxHere at nums[0]. The only subarray that ends at the first element is the element itself.
Create minHere at nums[0]. It is kept because a negative number turns the smallest product into the largest.
Create result at nums[0]. The subarray needs at least one element, so the first element alone is a valid start, even when it is negative.
Loop over the other elements with i from 1 while i < nums.size(). Index 0 is already counted.
Swap on a negative. If nums[i] < 0, call swap(maxHere, minHere). Multiplying by a negative number flips the order, so after the swap each variable is the one to multiply by nums[i].
Update maxHere: max(nums[i], maxHere * nums[i]). Either start fresh at i, or extend.
Update minHere: min(nums[i], minHere * nums[i]), the same two choices, keeping the smallest.
Update result: max(result, maxHere).
Return result after the loop.

The solution in C++

class Solution {
public:
    int maxProduct(vector<int>& nums) {
        int maxHere = nums[0];
        int minHere = nums[0];
        int result = nums[0];
        for (int i = 1; i < nums.size(); i++) {
            if (nums[i] < 0) {
                swap(maxHere, minHere);
            }
            maxHere = max(nums[i], maxHere * nums[i]);
            minHere = min(nums[i], minHere * nums[i]);
            result = max(result, maxHere);
        }
        return result;
    }
};

The C++ details worth a closer look:

swap, max and min. These come from the standard library. swap(a, b) exchanges the values of two variables, and max and min return the larger or smaller of two values of the same type. Both arguments here are int.
The order of the updates matters. maxHere is updated first, and the line for minHere uses minHere, not the new maxHere. The swap happens before both, so they stay a matched pair.
Signed overflow. Multiplying int values that don't fit is undefined behaviour in C++. The constraints say the product of any subarray fits in 32 bits, but minHere and maxHere only hold products of subarrays, so they stay within that range too. That guarantee is what makes plain int safe here.
Size and the loop index. nums.size() is unsigned, and i is an int. The comparison works for any realistic size, and the lesson guarantees at least one element, so reading nums[0] is safe.
Reference parameter. vector<int>& nums avoids copying a vector of up to 100,000 elements. The method doesn't change it.

Complexity

Time: O(n). The loop visits each element once, with a constant amount of work: one comparison, one possible swap and a few multiplications.

Space: O(1). Only three integers are kept, whatever the length of the vector.

Edge cases and common mistakes

A single element. [-3] returns -3. The loop doesn't run, and the answer is the first element. Starting result at 0 would wrongly return 0.
Zeros. [-2, 0, -1] returns 0. At the 0, both maxHere and minHere become 0, which cuts the product off from what came before. [0, 2] returns 2, since the 2 starts fresh.
Two negatives in a row. [-2, -3, -4] returns 12, from [-3, -4]. Taking all three would give -24. The best subarray can leave out the first negative.
An odd number of negatives. [2, -5, -2, -4, 3] returns 24, from [-2, -4, 3]. A method that only keeps the best product misses this, because the useful value is the most negative one carried through the swaps.
Keeping only maxHere. Without minHere, the -6 that the last -4 turns into 24 in [-2, 3, -4] is never remembered, and the answer 24 is missed.
Not starting fresh. Using maxHere * nums[i] alone, without the nums[i] option, carries a 0 forward forever and can't recover after it.
Updating minHere with the new maxHere. Both updates must use the values from before the current step, apart from the swap.

Testing

nums = [2, 3, -2, 4] gives 6.
nums = [-2, 0, -1] gives 0.
nums = [-2, 3, -4] gives 24.
nums = [-3] gives -3.
nums = [0, 2] gives 2.
nums = [-2, -3, -4] gives 12.
nums = [2, -5, -2, -4, 3] gives 24.

Keep going with C++500+ step-by-step lessons, from your first line of code to coding interviews. Free to start.

Start learning free