Maximum Product Subarray

Yukti Kumari
Last Updated: May 13, 2022

Introduction

In this article, you will learn ways to find the maximum product subarray. We will start with a brute force approach and then see ideas by which we can optimize the solution along with implementation in C++.

The problem statement is as follows:

Given an integer array nums, find a contiguous non-empty subarray within the array that has the largest product, and return the product.

Subarray - A contiguous subsequence of an array is called a subarray.

Example - Given an array [1,2,3,5,6], some of the subarrays are [1],[2],[3],[6],[1,2,3], [3,5,6] etc.

I strongly recommend giving an honest try at this problem and solve it by yourself before moving on to further discussions. You can solve it here - Maximum Product Subarray

Initial thoughts about solving the problem

  • It is an integer array i.e, the array may contain positivenegative and even zero integers.
  • Next, we have to deal with subarrays, so we can choose only contiguous segments of the array.
  • (Negative integer)*(Negative integer) = Positive integer ( I know, it may sound a bit childish to write this point but if you think about it, you realize it’s a key point for this problem).
  • (Positive integer)*(Negative integer) = Negative integer
  • (Positive integer)*(Positive integer) = Positive integer

Brute Force Method

We will first come up with a brute force approach to solve the problem.

Let’s see the steps to be followed - 

  1. Define a variable maximum_product to store the maximum product of the subarray found so far. 
  2. Initialize maximum_product to INT_MIN.
  3. We generate all the subarrays one by one and find the respective product of the subarray.
  4. For every subarray found, we will update the maximum product when the current product is greater than the current maximum product.

C++ Implementation

/* C++ code to find maximum product subarray of an array */
#include <iostream>
using namespace std;

/* function to find the maximum product of a subarray for a given array */
int findMaximumProduct(int arr[], int n)
{
    /* to store the maximum product subarray found so far */
    int max_so_far = 0;

    /* consider all subarrays starting from i */
    for (int i = 0; i < n; i++)
    {
        /* to store the current subarray product */
        int product = 1;

        /* consider all subarrays ending at j */
        for (int j = i; j < n; j++)
        {
            /* product of elements of the subarray arr[i,j] */
            product *= arr[j];

            /* update the maximum product if required */
            if (product > max_so_far)
            {
                max_so_far = product;
            }
        }
    }

  return max_so_far;
}

int main()
{
    int arr[] = {6-4-5807};
    int n = sizeof(arr) / sizeof(arr[0]);
    cout << "The maximum product subarray is " << findMaximumProduct(arr, n)<<endl;
    return 0;
}

 

Output:

The maximum product subarray is 960

 

Time Complexity - O(n^2) 

Since we check the product of all the subarrays for which we have used two loops. So, the time complexity is O(n^2).

Space Complexity - O(1)

We have not used any extra space to find the maximum product subarray. So, it has constant space complexity.

How to optimize?

If you know about Kadane’s Algorithm, then this problem is quite similar to this except for in this we have to find maximum product subarray instead of subarray sum.

Algorithm

  • Traverse the array and calculate the maximum and minimum product ending at the current index.
  • Update the result if the maximum product ending at any index is greater than the maximum product found so far.

 

For every index we have three possibilities:

  • When the current element is positive, then we may get the maximum product by the multiplication of the current number and the maximum product ending at the previous index.
  • When the current element is negative, then the product of the minimum product ending at the previous index and the current number might give the maximum product.
  • The maximum product subarray may start from the current index.

C++ Implementation

/* C++ code to find maximum product subarray of an array */
#include <bits/stdc++.h>
using namespace std;

/* function to find the maximum product of a subarray from given array*/
int findMaxProduct(int arr[], int n)
{
    /* define two variables to store the maximum and minimum product ending at the current index */
    int max_ending = arr[0], min_ending = arr[0];

    /* stores the maximum product subarray found so far */
    int max_so_far = arr[0];

    /* traverse the array */
    for (int i = 1; i < n; i++)
    {
        int temp = max_ending;

        /* update the maximum product ending at the current index*/
        max_ending = max(arr[i], max(arr[i] * max_ending, arr[i] * min_ending));

        /* update the minimum product ending at the current index*/
        min_ending = min(arr[i], min(arr[i] * temp, arr[i] * min_ending));

        max_so_far = max(max_so_far, max_ending);
    }

    return max_so_far;
}

int main(void)
{
    int arr[] = {6-4-5807};
    int n = sizeof(arr) / sizeof(arr[0]);

    cout << "The maximum product of a subarray is: " << findMaxProduct(arr, n) << endl;

    return 0;
}

 

Output:
The maximum product of a subarray is: 960

 

Time Complexity - O(n)

We iterate over the given array only once to find the maximum product subarray, so the time complexity is O(n), where n is the number of elements in the array.

Space Complexity - O(1)

The algorithm does not use any extra space, so the space complexity is O(1).

Key Takeaways

In this article, we discussed the solution to find the maximum product subarray. We saw two approaches: brute force method and then optimized it to get a solution with linear time complexity. The problem was quite similar to the famous Kadane’s Algorithm. You can check it out to understand better.

Planning to ace the interviews of reputed product-based companies like Amazon, Google, Microsoft, and more? Attempt our Online Mock Test Series on CodeStudio now!

Was this article helpful ?
0 upvotes

Comments

No comments yet

Be the first to share what you think