If you observe closely then, if the product of whole array is positive then it is the answer. If it’s negative then there are 3 cases:
Suppose an array is [a,b,c,d,e,f] where a,b,c,d,e,f are positive numbers. Now for a negative product whatever be the signs of b,c,d,e there are 3 possible combinations of signs of a and f:
Case 1: [-a,b,c,d,e,f]
Case 2: [-a,b,c,d,e,-f]
Case 3: [a,b,c,d,e,-f]
For Case 1: Ignore a and the suffix product subarray is the answer as they have even number of -ve signs.
For case 2: Ignore either a or b, ans is max of prefix product and suffix product at every point.
For Case 3: Ignore f and the prefix product subarray is the answer as they have even number of -ve signs.
All these cases boil down to max of prefix products starting from i=0 and max of suffix products starting from i=n-1.
Here’s the code:
int Solution::maxProduct(const vector<int> &arr) {
int n = arr.size();
if(n==0)
return 0;
if(n==1)
return arr[0];
int ans = 0;
int curr = 1;
for(int i=0;i<n;i++)
{
curr = curr*arr[i];
ans = max(ans,curr);
if(curr==0)
curr=1;
}
curr=1;
for(int i=n-1;i>=0;i--)
{
curr = curr*arr[i];
ans = max(ans,curr);
if(curr==0)
curr=1;
}
return ans;
}