Maximum Product Subarray

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]));
            ans=max(ans, max_prod);  //update answer
        }
        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]));
            ans=max(ans, max_prod);  //update answer
        }
        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

People are also reading:

• Difference Between Repeater, DataList and GridView
• Check if a subarray with 0 sum exists or not
• Diameter of a Binary Tree
• Subset Sum Problem
• Clone a Singly Linked List
• Subarray with Sum k
• Find Maximum Subarray Sum
• Maximum Sum Circular Subarray
• Longest? ?Bitonic? ?Subarray? ?Problem?
• Maximum of all Subarrays of size K