# Maximum Product Subarray

Posted in

Vinay Khatri
Last updated on August 10, 2024

## Problem

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

### Brute Force Approach

We can find all possible subarrays of a given array. It will work but is inefficient as the time complexity is O(N2).

### Efficient approach

We traverse every element in the array and keep track of minimum and maximum products so far. If we are at the current element, there can be three possible cases.

Case1 : The current element is greatest among maximum and minimum products.

Case2 : The current element is negative, and we are obtaining the maximum result by multiplying it by the previous minimum product.

Case3 : The current element is positive, and we are obtaining the maximum result by multiplying it by the previous maximum product.

At every element, we can get maximum from these conditions and update our answer. maximum =max(a[i]* maximum , a[i]* minimum , a[i]) - keep track of maximum product minimum =min(a[i]* maximum, a[i]* minimum, a[i]) - keep track of minimum product The time complexity of this approach is O(N).

### C++ Programming

```#include<bits/stdc++.h>
using namespace std;
int maxProduct(vector<int>& a) {
int min_prod=0;
int max_prod=0;
int ans=0;
int n=a.size();
if(n==1) return a[0];  //the answer will be that number itself
for(int i=0;i<n;i++){
int temp=max_prod;  //place maximum so far in temporary variable
max_prod=max(max_prod*a[i], max(min_prod*a[i], a[i]));
min_prod=min(temp*a[i], min(min_prod*a[i], a[i]));
}
return ans;
}
int main(){
vector<int>a{1, 2, 4, -4};
cout<<maxProduct(a);
}```

Output

`8`

### C Programming

```#include<stdio.h>
int max(int a, int b){
if(a>=b) return a;
return b;
}
int min(int a, int b){
if(a>=b) return b;
return a;
}
int maxProduct(int* a, int n){
int min_prod=0;
int max_prod=0;
int ans=0;
if(n==1) return a[0];  //the answer will be that number itself
for(int i=0;i<n;i++){
int temp=max_prod;  //place maximum so far in temporary variable
max_prod=max(max_prod*a[i], max(min_prod*a[i], a[i]));
min_prod=min(temp*a[i], min(min_prod*a[i], a[i]));
}
return ans;
}

int main(){
int a[5]={1, 2, -1, 4};
int n=sizeof(a)/sizeof(a[0]);
printf("%d",maxProduct(a,n));
}```

Output

`4`

### Python Programming

```def maxProduct(a):
if len(a)==0:
return 0

max_so_far , min_so_far = a[0], a[0]

#ans will store the final max product
ans = max_so_far

for i in range(1, len(a)):
element = a[i]

temp_max = max( element ,  max_so_far*element, element*min_so_far)

min_so_far = min( element ,  max_so_far*element, element*min_so_far)

max_so_far = temp_max

ans = max(ans, max_so_far) #update answer

return ans

l = [1, 2, -1, 3];
print(maxProduct(l))```

Output

`3`