Initial thoughts about solving the problem
- It is an integer array i.e, the array may contain positive, negative, 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 -
- Define a variable maximum_product to store the maximum product of the subarray found so far.
- Initialize maximum_product to INT_MIN.
- We generate all the subarrays one by one and find the respective product of the subarray.
- 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;
}
You can also try this code with Online C++ Compiler
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;
}
You can also try this code with Online C++ Compiler
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).
Frequently Asked Questions
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!
34+ registered 
