Lesson 4: MaxProductOfThree (Max Product of Three)

これはちょっとしたトリックでO(N)で解ける問題です。ソートしなくても良いのです。

３つの値を選んだとき、全て正の値なら当然大きいもの３つをかければいいのですが、ここで負の数が二つあった時の事を考えてみてください。そうすると負x負は正になりますね。

そう考えると大きい方から値３つと　小さいから値２つと最大の値１つ、それぞれの積が大きい方を選べば一番大きい値が得られます。

この為にはソートしないでも一回だけ配列をスキャンすればいいですね。

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