1.
Introduction
2.
Problem Statement
3.
Initial thoughts about solving the problem
4.
Brute Force Method
4.1.
C++ Implementation
5.
How to optimize?
5.1.
Algorithm
5.2.
C++ Implementation
6.
6.1.
What is a Subarray?
6.2.
What is a Subsequence?
6.3.
What is the Time and Space Complexity of Kadane's Algorithm?
7.
Conclusion
Last Updated: Mar 27, 2024
Medium

# Maximum Product Subarray

Yukti Kumari
0 upvote

## 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++.

## Problem Statement

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.

Thus the maximum product of a sub-array in this example is 180

Recommended: Try the Problem Maximum Product Subarray yourself first before moving on to the solution.

Get the tech career you deserve, faster!
Connect with our expert counsellors to understand how to hack your way to success
User rating 4.7/5
1:1 doubt support
95% placement record
Akash Pal
Senior Software Engineer
326% Hike After Job Bootcamp
Himanshu Gusain
Programmer Analyst
32 LPA After Job Bootcamp
After Job
Bootcamp

## 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, -5, 8, 0, 7};
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 in this we have to find the maximum product subarray instead of the 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, -5, 8, 0, 7};
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).

### What is a Subarray?

A Subarray is a contiguous segment of an array starting from any index of an array to any valid number of elements

### What is a Subsequence?

A subsequence is a sequence of elements obtained from any string or array not necessarily continuous but maintaining the original order of occurrence as in the original sequence,

### What is the Time and Space Complexity of Kadane's Algorithm?

The time complexity of Kadane's Algorithm is O(N) where N is the number of elements and the space complexity is O(1) which is constant.

## Conclusion

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.

Recommended Problems:

Check out some of the amazing Guided Paths on topics such as Data Structure and Algorithms, Competitive Programming, Basics of C, etc. along with some Contests and Interview Experiences only on Coding Ninjas Studio

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

Live masterclass