Maximum product subarray

Why this matters

Many programs look for the best run of values in a list. A trading tool might ask which run of daily price changes, multiplied together, gives the largest total growth. A sensor tool might ask which run of readings gives the strongest combined signal. Each question asks for a contiguous run, which means a block of neighbouring values with no gaps.

The sum version of this question is a classic beginner exercise. You keep a running total and reset it when it goes below zero. The product version looks similar, but it breaks that habit. A product can flip from a small number to a very large one, and it can flip back, because multiplying by a negative number changes the sign. This lesson shows how to handle that with a dynamic programming idea: keep two running answers at each step, not one.

Contiguous runs and products in plain words

A contiguous run is a block of neighbouring values. In the list 2, 3, -2, 4, the run 3, -2 is contiguous, and so is the run 2, 3. The values 2 and 4 together are not contiguous, because -2 sits between them.

A subarray is a contiguous run inside an array. In C++ an array is often a std::vector. The product of a subarray is every value in it multiplied together. The product of 2, 3 is 6. The product of 3, -2 is -6.

The task is to find the subarray whose product is largest. The result can be negative when every subarray is negative. A single value is always a subarray, so the answer is never empty when the list has at least one value.

Why the simple approach fails

A beginner often tries this: keep a running product, and when it becomes less than the current value, start again from the current value. This works for sums, but it does not work for products.

Take -2, 3, -4. The best run is the whole list, because -2 times 3 times -4 equals 24. The simple approach starts with -2. Then it multiplies by 3 to get -6, which is less than 3, so it starts again at 3. Then it multiplies by -4 to get -12, which is less than -4, so it starts again at -4. The best answer it saw was 3. The correct answer is 24.

The mistake is that the run with the most negative product, -6, was thrown away. Multiplying -6 by the next value -4 gives 24. A negative number times a negative number is positive. A large negative product can become the largest product after one more negative value. So the program must remember the most negative product too.

The idea: keep the largest and the smallest

At each position, track two numbers:

• curMax, the largest product of any subarray that ends at this position.
• curMin, the smallest product of any subarray that ends at this position.

Both are needed because of how multiplication works. Multiplying by a positive value keeps the order: the largest stays the largest. Multiplying by a negative value reverses the order: the largest becomes the smallest, and the smallest becomes the largest. So when the current value x is negative, the old curMin can produce the new curMax.

For each new value x, the subarray that ends at x has one of three forms:

• It is just x by itself, so the product is x.
• It extends a subarray that had the largest product, so the product is curMax * x.
• It extends a subarray that had the smallest product, so the product is curMin * x.

The new curMax is the largest of those three. The new curMin is the smallest of those three. Then the answer is the largest curMax seen at any position.

This is dynamic programming in a plain form. Each step uses only the answers from the step before, so the program keeps two numbers and moves forward once through the list.

Worked example 1: 2, 3, -2, 4

Start with the first value. The best subarray ending there is the value itself, so curMax, curMin and the answer are all 2.

Each row below shows one step. The three candidates are x by itself, curMax * x, and curMin * x.

At x = 3, the run extends to 2, 3 with product 6. That is larger than 3 by itself, so curMax becomes 6. The smallest product ending at 3 is 3 by itself, so curMin becomes 3.

At x = -2, the best product ending here is -2 by itself, because the candidates -12 and -6 are both smaller. The smallest product is -12, from 2, 3, -2. Keeping -12 matters for the next step.

At x = 4, the answer does not change. The best subarray with 4 at the end is 4 by itself. The best overall answer stays 6, which comes from 2, 3.

The final answer is 6.

Worked example 2: -2, 3, -4

This is the list that broke the simple approach. Here the smallest product is what leads to the answer.

At x = -4, the candidate curMin * x is -6 * -4, which equals 24. The product of -2, 3, -4 is the same 24, so the whole list is the best run. The simple approach missed this, because it did not keep -6.

The final answer is 24.

Worked example 3: a zero in the list

A zero is special, because any product that includes it is 0. Here is -2, 0, -1:

At x = 0, every candidate is 0, so both running values reset to 0. The zero acts like a wall. Nothing before it can multiply into anything after it. At x = -1, the candidate x by itself is -1, and the candidates that include the zero are 0. So curMax becomes 0, and the answer stays 0.

The program needs no special case for zero. The three candidates handle it.

The example shows one more point. The answer is 0, not -2, because the single value 0 is a subarray with product 0, and 0 is larger than -2. A subarray that includes the zero is a better answer than any negative product.

A longer example: 2, -5, -2, -4, 3

This list has several negatives, so the running values change sign many times. A trace of the steps, worked out by hand, is:

start x=2 max=2 min=2 best=2
x=-5 candidates -5, -10, -10 -> max=-5 min=-10 best=2
x=-2 candidates -2, 10, 20 -> max=20 min=-2 best=20
x=-4 candidates -4, -80, 8 -> max=8 min=-80 best=20
x=3 candidates 3, 24, -240 -> max=24 min=-240 best=24
answer 24

At x = -2, the candidate curMin * x is -10 * -2 = 20. That is the product of 2, -5, -2, which is 20. The subarray -5, -2 gives 10, but the longer run that starts at 2 is better.

At x = 3, the candidate curMax * x is 8 * 3 = 24. That is the product of -2, -4, 3. The answer 24 is the largest of all the curMax values, so it is the final answer.

The code

The program keeps best, curMax and curMin. The loop computes the three candidates once and stores the results in new variables before updating the running values. The new values must be computed from the old ones, so the program does not overwrite curMax too early.

#include <algorithm>
#include <iostream>
#include <vector>
 
// Returns the largest product of a contiguous, non-empty part of a.
// Requires a to be non-empty.
long long maxProductSubarray(const std::vector<long long>& a) {
    long long best = a[0];
    long long curMax = a[0];  // largest product of a subarray that ends at the current index
    long long curMin = a[0];  // smallest product of a subarray that ends at the current index
    for (std::size_t i = 1; i < a.size(); ++i) {
        long long x = a[i];
        long long newMax = std::max({x, curMax * x, curMin * x});
        long long newMin = std::min({x, curMax * x, curMin * x});
        curMax = newMax;
        curMin = newMin;
        best = std::max(best, curMax);
    }
    return best;
}
 
int main() {
    std::cout << maxProductSubarray({2, 3, -2, 4}) << "\n";
    std::cout << maxProductSubarray({-2, 3, -4}) << "\n";
    std::cout << maxProductSubarray({-2, 0, -1}) << "\n";
    std::cout << maxProductSubarray({2, -5, -2, -4, 3}) << "\n";
    std::cout << maxProductSubarray({-1, -2, -3, 0}) << "\n";
    std::cout << maxProductSubarray({-2, 7}) << "\n";
    std::cout << maxProductSubarray({-5}) << "\n";
    std::cout << maxProductSubarray({100000LL, 100000LL, 3}) << "\n";
}

The function std::max with a list of three values, written std::max({a, b, c}), needs <algorithm>. The braces make a list of values, and the standard library returns the largest one. std::min works the same way for the smallest.

Each step reads curMax and curMin from the step before, so the program needs only those two values. It does not store a table with one row per position. That makes the memory use constant, which means the amount of memory does not grow with the length of the list.

Running the program

Save the program above as p12_final.cpp. Compile and run from the folder that holds the file.

g++ -std=c++20 -Wall -Wextra -o p12_final p12_final.cpp
./p12_final

The output is:

6
24
0
24
6
7
-5
30000000000

The first four lines match the hand traces above. The other four are these. -1, -2, -3, 0 gives 6 from the run -2, -3. -2, 7 gives 7, because the run -2, 7 gives -14 and the single value 7 is larger. -5 gives -5, because a single value is the only choice. The last line uses long long, so the product of 100000 * 100000 * 3 fits and prints in full.

The program was also compared with a brute-force check that tries every subarray. The check covered 5,000 random lists of length 1 to 8, with values from -5 to 5, and found no differences. Brute force means trying all the choices, which is slow but easy to trust.

Overflow and the size of the answer

The product grows fast. Each extra value can multiply the answer by a large amount, so the answer may not fit in the type you chose. An int on most current systems holds values up to about 2.1 billion. A long long holds values up to about 9.2 quintillion.

Here is the same idea with int. The program below multiplies 100000 by 100000 as int values:

#include <iostream>
#include <vector>
 
int main() {
    std::vector<int> a = {100000, 100000, 3};
    int p = 1;
    for (int x : a) p *= x;
    std::cout << "int product: " << p << "\n";
    std::vector<long long> b = {100000, 100000, 3};
    long long q = 1;
    for (long long x : b) q *= x;
    std::cout << "long long product: " << q << "\n";
}

A normal build prints a wrong result and gives no warning:

int product: -64771072
long long product: 30000000000

The true product is 30,000,000,000, which is too large for an int. In C++, signed integer overflow is undefined behaviour. That means the language does not promise any result, so the printed number is not meaningful. When the same program is built with -fsanitize=undefined, the checker prints the reason at the overflow. By default it keeps running, so the wrong number is still printed:

overflow.cpp:7:23: runtime error: signed integer overflow: 100000 * 100000 cannot be represented in type 'int'

Use long long for products, and check the limits given in the problem. If the product can exceed what long long holds, the problem needs a different approach, such as working with logarithms or with big-number types.

Common mistakes

Tracking only the largest product

This is the mistake described earlier. For -2, 3, -4, the program that tracks only curMax returns 3. The correct answer is 24, because the negative product -6 becomes positive when it is multiplied by -4. The fix is to track curMin as well.

Resetting to 1 or 0, as in the sum version

Some people reset the running product to 1 when it becomes small, or to 0 when it becomes negative, copying the sum method. Both resets throw away information. A reset to 0 hides negative runs that can flip later, and a reset to 1 counts a run that was never there. Use the value x itself as the new start, which the candidate list already does.

Updating curMax before computing curMin

The new curMin needs the old curMax, and the new curMax needs the old curMin. If the program writes the new curMax into the variable first, the next line reads the new value by mistake. The fix is to store both new values in temporary variables, as the program does, and then assign them.

Using an empty list

The program starts with a[0]. If the list is empty, that is a read past the end of the vector. Without checks, the program may print garbage or crash. With the standard library's index checks turned on, the program stops with a clear message. Building with -D_GLIBCXX_ASSERTIONS and calling the function with an empty vector prints a long line. The start is the path of a standard library header, which differs by machine. It ends like this:

Assertion '__n < this->size()' failed.

The fix is to check a.empty() first and return an agreed value, or to state in the problem that the list is never empty.

Practice

Exercise 1

Find the largest product of a subarray in -1, -2, -3, 0. Then check the answer with the program.

Show the answer

The answer is 6. The run -2, -3 has product 6. The full list has product 0, which is smaller. The zero at the end cannot help, because any run that includes it has product 0.

Exercise 2

Trace the program on -2, 7. Give the three candidates and the new curMax and curMin at the second value.

Show the answer

At x = 7, the candidates are 7, -2 * 7 = -14 and -2 * 7 = -14, because curMax and curMin both equal -2 after the first value. The new curMax is 7 and the new curMin is -14. The answer is 7.

Exercise 3

Explain why the simple approach that resets the running product returns 3 on -2, 3, -4, and what it should have kept.

Show the answer

The simple approach keeps -2, then multiplies to get -6. It sees that -6 is less than 3 and restarts at 3. Then 3 * -4 = -12, which is less than -4, so it restarts at -4. The best it saw is 3. It should have kept -6, because -6 * -4 = 24. That is why the minimum must be tracked.

Exercise 4

Give the answer for the one-value list -5, and explain why the answer is not 0.

Show the answer

The answer is -5. A subarray must hold at least one value, and the only subarray is -5 itself. The product 0 would need a subarray with a zero in it, and the list has none.

Exercise 5

Write the candidates for x = -4 when curMax is 8 and curMin is -80. Then give the new curMax and curMin.

Show the answer

The candidates are -4, 8 * -4 = -32, and -80 * -4 = 320. The new curMax is 320, and the new curMin is -32. This is the case where the old smallest product becomes the new largest one.

Summary

• The largest product can come from a run whose running product was very negative until a later negative value flipped it positive.
• At each position, track the largest and the smallest product of a subarray that ends there.
• The three candidates at each step are the value by itself, the old maximum times the value, and the old minimum times the value.
• The answer is the largest running maximum seen at any position, and the method takes O(n) time with constant memory.
• Use long long for products, and watch for overflow, which is undefined behaviour for int.