Lesson 4: MaxProductOfThree (Max Product of Three)

The trick is to produce a max product, we have to consider any two of the three picked up values can be negative. In this case, the product of these two negative values can be positive.

So what we need to do is to compute the product of two smallest values and one biggest values and the product of three biggest values.

The bigger one of these two will be the maximum product.

This is indeed a O(N) time complexity problem,
as we don't even have to sort the array. We just have to obtain two minimum values and three biggest values for this strategy.

--------------------------------
SOLUTION
--------------------------------
int solution(int A[], int N) 
{
    if (N == 3){
        return A[0] * A[1] * A[2];
    }
    int max1 = -1001;  
    int max2 = -1001;    
    int max3 = -1001;   
    
    int min1 = 1001;   
    int min2 = 1001;      
    int i;        
    for (i = 0; i < N; i++){
        int tmp = A[i];
        if (tmp > max1){
            max3 = max2;
            max2 = max1;
            max1 = tmp;
        }     
        else if (tmp > max2){
            max3 = max2;
            max2 = tmp;
        }         
        else if (tmp > max3){
            max3 = tmp;
        }
        
        if (tmp < min1){  
            min2 = min1;   
            min1 = tmp;    
        }      
        else if (tmp < min2){
            min2 = tmp;
        }   
    }        
    
    int val1 = max1 * max2 * max3;    
    int val2 = max1 * min1 * min2;  
    
    return val1 > val2 ? val1 : val2;
}