Easy, Intuitive and Understandable Logic Clean C++ Code


#1

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;
}