Maximum Product Subarray

DevSniper
Published : 26 July 2024

198 Views

Given an integer array arr (positive and negative numbers) of size N, your task is to find a subarray that has the largest product.

Example 1 :-

[2,5,3,-2,4,10,2]

Output : 80

Example 2 :-

[2,-5,-3,-2,4,10,2]

Output : 480

Example 3 :-

[-6,0,-1]

Output : 0

Constraints :

N = arr.length
1 <= N <= 2 * 10^4
-10 <= arr[i] <= 10
The product of any prefix or suffix of arr is guaranteed to fit in a 32-bit integer.

Brute Force Approach

Brute Force approach involves using nested loops. The outer loop selects the starting element, while the inner loop calculates the maximum possible product from starting element. It compares each local maximum with the overall maximum product if local product if greater than overall maximum product then update overall maximum product with local product. At the end of both loop overall maximum product contains maximum product subarray.

C++

Java

Python

#include <bits/stdc++.h>
using namespace std;

int FindMaxProductSubArray(int arr[], int n)
{
    int maxProduct=arr[0];
    for(int i=0; i<n-1; i++) {
        int localProduct=arr[i];
        for(int j=i+1; j<n; j++) {
            maxProduct = max(maxProduct,localProduct);
            localProduct*=arr[j];
        }
        maxProduct = max(maxProduct,localProduct);
    }
    return maxProduct;
}
int main()
{
    int arr[] = {10, -6, 1, 2, 8};
    int n = sizeof(arr) / sizeof(arr[0]);
    cout << FindMaxProductSubArray(arr,n) <<endl;
}

Time Complexity : O(N^2)

Space Complexity : O(1)

Using Two Pointer

Observations :

If all elements in the given array are positive, then the maximum product subarray will simply be the product of all the elements in the array.
If the array contains even number of negative elements, then the maximum product subarray will be the product of the entire array.
If the array has odd number of negative elements, we have to remove one negative number to maximize the product of the remaining subarray. To achieve this we need to decide which one negative number to remove such that the remaining subarray produce the maximum product.
Lets Understand with an Example :-
```
arr : [ 2, -3, 4, -5, 10, 8, -2, 3]
removing : -3
 [ 2] and  [4, -5, 10, 8, -2, 3] => subarray products are 2 and 9600
removing : -5
 [ 2, -3, 4] and  [10, 8, -2, 3] => subarray products are -24 and -480
removing : -2
 [ 2, -3, 4, -5, 10, 8] and [ 3] => subarray products are 9600 and 3
```
- when we remove one negative number array will be divides into two parts.
- The answer will be either the left or right subarray product.
- To find the final answer, we will check all possible subarrays for all negative numbers.

If the array contains zeros, we will not consider zero's in our answer so zeros divide the array into separate subarrays. We then calculate the maximum product subarray for each subarrays and take the highest product from these subarrays.

Lets Understand with an Example :-

arr : [ 2, -3, 0, -5, -6, 0, 8, -2, 3]
subarrays after removing 0's
[ 2, -3] , [-5, -6]  and [8, -2, 3]
we will find maximum product subarray of these arrays
[ 2, -3] => 2
[-5, -6] => 30
[8, -2, 3] => 8
Now final answer will be maximum of these 
 max of ( 2, 30 , 8) => 30
So the final answer will be => 30

Instead of developing each case individually as discussed above, we can design an optimal solution that incorporates all these observations and handles each scenario effectively.

Algorithm :

We will maintain a variable (maxProduct) for max product and traverse the array, multiply elements and update maxProduct if the current product is greater. If element is 0 then make current products of all elements till now equal to 1 because from the next element, we will start a new subarray. There will be a problem when array will contain odd number of negative number because here we need to remove one negative number. Since we are considering subarray so we can’t simply remove any one negative element. We need to carefully manage them by either removing the first or the last negative number. When we traverse from start then we can remove last negative number and if from end then first so to over these cases we can iterate array from both side start and end computing the product in each case and comparing the results to ensure the maximum product subarray is identified. This approach ensures that you handle all scenarios and find the optimal solution efficiently.

Steps :

Declare and initialize variables leftProduct =1 , rightProduct =1 and maxProduct=Min_Value
Iterate array from start to end.
If either leftProduct or rightProduct is 0, set it to 1.
Multiply the corresponding elements in leftProduct and rightProduct.
update maxProduct with maximum of maxProduct , leftProduct and rightProduct
At the end of iteration maxProduct will contains the maximum product subarray.

C++

Java

Python

#include <bits/stdc++.h>
using namespace std;

int FindMaxProductSubArray(int arr[], int n)
{
    int leftProduct=1,rightProduct=1;
    int maxProduct = INT_MIN;
    for (int i = 0; i < n; i++) {
        if(leftProduct==0) {
            leftProduct=1;
        }
        if(rightProduct==0) {
            rightProduct=1;
        }
        leftProduct*=arr[i];
        rightProduct*=arr[n-i-1];
        maxProduct=max(maxProduct,max(rightProduct,leftProduct));
    }
    return maxProduct;
}
int main()
{
    int arr[] = {10, -6, 1, 2, 8, -2, -3};
    int n = sizeof(arr) / sizeof(arr[0]);
    cout << FindMaxProductSubArray(arr,n) <<endl;
}

Time Complexity : O(N)

Space Complexity : O(1)

Using Kadane’s Algorithm

Kadane’s Algorithm is used to find the maximum subarray product of an array of numbers efficiently in O(N) time complexity.

We will maintain three variables (currentMaxProduct , currentMinProduct and maxProduct). currentMaxProduct which tracks the maximum product of a contiguous subarray ending at the current index, currentMinProduct tracks the minimum product of a contiguous subarray ending at the current index and maxProduct stores the overall maximum product found so far. During each iteration if currentMaxProduct exceeds maxProduct update maxProduct with currentMaxProduct . By the end of the iteration maxProduct represents the maximum subarray product of the array.

Steps :

Declare and initialize variables currentMaxProduct=1,currentMinProduct=1 and maxProduct=MIN Value;
Iterate array from start to end and do below tasks
Caclulate currentMaxProduct that is maximum of arr[i] , currentMaxProduct* arr[i] and currentMinProduct*arr[i]
Calculate currentMinProduct that is minimum of arr[i], currentMaxProduct*arr[i] and currentMinProduct*arr[i]
update maxProduct with maximum of calculated currentMaxProduct and maxProduct
After completion of the iteration maxProduct will contains maximum product subarray.

C++

Java

Python

#include <bits/stdc++.h>
using namespace std;

int FindMaxProductSubArray(int arr[], int n)
{
    int currentMaxProduct=1,currentMinProduct=1;
    int maxProduct=INT_MIN;
    int temp=0;
    for(int i=0; i<n; i++) {
        temp = max(arr[i],max(currentMaxProduct*arr[i],currentMinProduct*arr[i]));
        currentMinProduct = min(arr[i],min(currentMaxProduct*arr[i],currentMinProduct*arr[i]));
        currentMaxProduct= temp;
        maxProduct = max(maxProduct,currentMaxProduct);
    }
    return maxProduct;
}
int main()
{
    int arr[] = {10, -6, 1, 2, 8, -2, -3};
    int n = sizeof(arr) / sizeof(arr[0]);
    cout << FindMaxProductSubArray(arr,n) <<endl;
}

Time Complexity : O(N)

Space Complexity : O(1)