Maximum Product Subarray | Added negative product case | C ++ program to find maximum subarray product . ; Function to find maximum subarray product . ; As maximum product can be negative , so initialize ans with minimum integer value . ; Variable to store maximum product until current value . ; Variable to store minimum product until current value . ; Variable used during updation of maximum product and minimum product . ; If current element is positive , update maxval . Update minval if it is negative . ; If current element is zero , maximum product cannot end at current element . Update minval with 1 and maxval with 0. maxval is updated to 0 as in case all other elements are negative , then maxval is 0. ; If current element is negative , then new value of maxval is previous minval * arr [ i ] and new value of minval is previous maxval * arr [ i ] . Before updating maxval , store its previous value in prevMax to be used to update minval . ; Update ans if necessary . ; If maxval is zero , then to calculate product for next iteration , it should be set to 1 as maximum product subarray does not include 0. The minimum possible value to be considered in maximum product subarray is already stored in minval , so when maxval is negative it is set to 1. ; Driver Code
#include <bits/stdc++.h> NEW_LINE using namespace std ; int findMaxProduct ( int arr [ ] , int n ) { int i ; int ans = INT_MIN ; int maxval = 1 ; int minval = 1 ; int prevMax ; for ( i = 0 ; i < n ; i ++ ) { if ( arr [ i ] > 0 ) { maxval = maxval * arr [ i ] ; minval = min ( 1 , minval * arr [ i ] ) ; } else if ( arr [ i ] == 0 ) { minval = 1 ; maxval = 0 ; } else if ( arr [ i ] < 0 ) { prevMax = maxval ; maxval = minval * arr [ i ] ; minval = prevMax * arr [ i ] ; } ans = max ( ans , maxval ) ; if ( maxval <= 0 ) { maxval = 1 ; } } return ans ; } int main ( ) { int arr [ ] = { 0 , -4 , 0 , -2 } ; int n = sizeof ( arr ) / sizeof ( arr [ 0 ] ) ; cout << findMaxProduct ( arr , n ) ; return 0 ; }