Maximum Product Subarray

Posted in

Maximum Product Subarray

Vinay Khatri
Last updated on June 9, 2022

    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 for every element in the array and keep track of minimum and maximum product 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 with the previous minimum product. Case3 : The current element is positive and we are obtaining the maximum result by multiplying it with 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:

    Leave a Comment on this Post

    0 Comments