Monday, 1 January 2018

C++ Program to find Maximum Product Subarray

In this question an array of positive and  negative integers is given to you. You have to find the maximum product of subarray. C++ complete program to get the maximum product subarray is given below.

Example:


Input : [2, 3, -2, 4]
Return : 6 

Possible with [2, 3]

PROGRAM:


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

int maxProduct(const vector<int> &A) {
     
      /*This code will handle the following test cases: A[]= {0.2.0,0,23}
                                                        A[]={ 0,0,0,1}

      */

      bool together=false;
      int maxi=0;
      for(int i=0;i<A.size()-1;i++){
            if(A[i]!=0 && A[i+1]!=0) together=true;
            if(maxi<A[i]){
                 maxi=A[i];
            }
          
      }


      if(maxi<A[A.size()-1]) maxi=A[A.size()-1];
      if(!together) return maxi; 



      /*Rest of the case will be hanlded by the code given below*/
    
      int max_ending_here=1,max_so_far=1,min_ending_here=1;
      for(int i=0;i<A.size();i++){
              if(A[i]>0){
                    max_ending_here=max_ending_here*A[i];
                    min_ending_here=min(min_ending_here*A[i],1);
              }
              else if(A[i]==0){
                    max_ending_here=1;
                    min_ending_here=1;
              }
              else{
                    int temp=max_ending_here;
                    max_ending_here=max(min_ending_here*A[i],1);
                    min_ending_here=temp*A[i];
              }
              
              if(max_so_far<max_ending_here){
                   max_so_far=max_ending_here;
              }
      }
      return max_so_far;
}
int main(){
    
    
      int n;

      cout<<"\nEnter the total number of elements: \n";
      cin>>n;

      cout<<"\nEnter the elements of array:\n";
      int num;

      std::vector<int> A;

      for(int i=0;i<n;i++){
           cin>>num;
           A.push_back(num);
      }
     
      int result=maxProduct(A);
      cout<<"\nThe maximum subarray product is: "<<result;
      return 0;
}

OUTPUT:





EmoticonEmoticon