# L6-MaxProductOfThree
###### tags:`Codility_lessons`
## Question
https://app.codility.com/programmers/lessons/6-sorting/max_product_of_three/
## Key
1. 用三個loop算出所有相乘可能，並找出最大的值，但這樣會有些例子會time exceed
2. 可以先做sorting再相乘，就可以縮減到一個loop，注意因為有兩個負值相乘可能比兩個正的最大值還大，所以不能直接將sorting後的倒數三個數相乘
3. 或是可以用一個loop做排序，直接在排序過程找出最小的兩個負值，還有最大的三個正值，最後比較兩種可能產生最大結果
## Reference
## Solution

### Sol.1

#include <algorithm>
int solution(vector<int> &A) {
    // write your code in C++14 (g++ 6.2.0)
    vector<int>&s(A);
    sort(s.begin(),s.end());
    long ans = 0; 
    for(unsigned int i=0; i<s.size()-2; i++)
    {
        if(i==0)
        {
            ans = (long)s[i]*(long)s[i+1]*(long)s[i+2];
        }
        else
        {
            if((long)s[i]*(long)s[i+1]*(long)s[i+2]>ans)
            {
                ans = (long)s[i]*(long)s[i+1]*(long)s[i+2];
            }
        }
    }
    if((long)s[0]*(long)s[1]*(long)s[s.size()-1]>ans)
    {
        return (long)s[0]*(long)s[1]*(long)s[s.size()-1];
    }
    else
        return ans;
}

### Sol.2

int solution(vector<int> &v) {

    vector<int> max_num(3,-1000);
    vector<int> min_neg(2,0);    
	const int v_size = v.size();    
	for (auto i = 0; i < v_size; ++i) {
        if (v[i] < min_neg[0] ) {
            min_neg[1]=min_neg[0];
            min_neg[0]=v[i];
        }
        else if (v[i] < min_neg[1]) {
            min_neg[1]=v[i];
        }
        if (v[i] > max_num[0]) {
            max_num[2]=max_num[1];
            max_num[1]=max_num[0];
            max_num[0]=v[i];
        }
        else if (v[i] > max_num[1]) {
            max_num[2]=max_num[1];
            max_num[1]=v[i];
        }
        else if (v[i] > max_num[2]) {
            max_num[2]=v[i];
        }
    }  
	
	auto res_neg = max_num[0] * min_neg[0] * min_neg[1];
    auto res_pos = max_num[0] * max_num[1] * max_num[2];
    return max (res_pos, res_neg);
}