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$ .

Steps

The algorithm is as follows:

Initialize $prod\_max$ , $prod\_min$ and $overall\_max$ to the first element of the array.
Begin iterating the array.
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).
Update $prod\_max$ , $prod\_min$ and $overall\_max$ as discussed above.
Once the array is completely traversed, return $overall\_max$ as the answer.

The example below visually demonstrates how this algorithm works:

#include <iostream>
using namespace std;
int maxProductofSubarray(int* arr, int N){
  // initializing prod_max, prod_min and overall_max
  int prod_max = arr[0];
  int prod_min = arr[0];
  int overall_max = arr[0];
  for(int i=0 ; i<N; i++)
  {
    if(arr[i] < 0) // checking if negative
    {
      int temp = prod_max ;
      prod_max = prod_min ;
      prod_min = temp ;
    }
    // prod_max = max(arr[i] , arr[i] * prod_max)
    if(arr[i] > arr[i]*prod_max) 
    {
      prod_max = arr[i];
    }
    else
    {
      prod_max = arr[i] * prod_max ; 
    }
    // prod_min = min(arr[i] , arr[i] * prod_min)
    if(arr[i] < arr[i]*prod_min)
    {
      prod_min = arr[i];
    }
    else
    {
      prod_min = arr[i] * prod_min ;
    }
    // overall_max = max(overall_max , prod_max)
    if(prod_max > overall_max)
    {
      overall_max = prod_max ;
    }
    else
    {
      overall_max = prod_min ;
    }
  }
  return overall_max ;
}
int main() 
{
  int arr[6] = {1, 2, -3, 0, -4, -5};
  int N = 6;
  int max_prod_of_a_subarray = maxProductofSubarray(arr , N);
  cout << "The maximum product of a sub-array is: " << max_prod_of_a_subarray << endl ;
  return 0;
}

How to find the maximum product subarray in a given array

Simple solution

Efficient solution

Steps

Code example

Code explanation