How to find the maximum product subarray in a given array

Given a fixed-size array containing $N$ integers, we can find the maximum product possible from all its sub-arrays. For example, given the array $[2,3,-2,4]$, the maximum product of a sub-array in it is $6$, which belongs to the sub-array $[2,3]$.

Simple solution

One approach is to generate all possible sub-arrays and return the maximum product after evaluating the product of each sub-array. However, this is a very inefficient solution as it will take $O(N^2)$ time in the worst case (this is because generating all possible subarrays requires one loop to be nested inside the other).

In this Answer, we'll explore how a more efficient solution can be implemented for this task, which takes $O(N)$time in the worst case.

Efficient solution

To efficiently solve this problem, we need to keep track of 3 products while iterating through the array. The products are as follows:

• The current maximum product ($prod\_max$): This will be the maximum of the current element during the traversal and the product of the current element with $prod\_max$.

• The current minimum product ($prod\_min$): This will be the minimum of the current element during the traversal and the product of the current element with $prod\_min$.

• The overall largest product encountered ($overall\_max$): This will be the largest value of $prod\_max$ that has been encountered so far.

Steps

The algorithm is as follows:

1. Initialize $prod\_max$, $prod\_min$ and $overall\_max$ to the first element of the array.

2. Begin iterating the array.

3. If the current element is negative, swap the values of $prod\_max$ and $prod\_min$. (When these products are updated later, multiplying the maximum value with a negative value will make it the minimum, and multiplying the minimum value with a negative value will make it the maximum).

4. Update $prod\_max$, $prod\_min$ and $overall\_max$ as discussed above.

5. Once the array is completely traversed, return $overall\_max$ as the answer.

The example below visually demonstrates how this algorithm works:

Code example

The code below implements the logic discussed above in C++ and Python:

Code explanation

The important lines in the code are explained below:

• Lines 6 – 8: We initialize prod_max, prod_min and overall_max to arr[0].

• Lines 20 – 27: We update prod_max such that prod_max is max(arr[i], arr[i] * prod_max).

• Lines 30 – 37: We update prod_min such that prod_min is min(arr[i], arr[i] * prod_min).

• Lines 40 – 47: We update overall_max such that overall_max is max(overall_max, arr[i] * overall_max).