Maximum Product of Three Numbers 三个数字的最大乘积

/**

参考：
　　https://www.cnblogs.com/grandyang/p/7084957.html

 * @brief The Solution class
 * Given an integer array, find three numbers whose product is maximum and output the maximum product.
 
Example 1:

Input: [1,2,3]
Output: 6
 

Example 2:

Input: [1,2,3,4]
Output: 24
 

Note:

The length of the given array will be in range [3,104] and all elements are in the range [-1000, 1000].
Multiplication of any three numbers in the input won't exceed the range of 32-bit signed integer.
 */

class Solution{
public:
    int maximumProduct(vector<int>& nums){
        int n = nums.size();
        sort(nums.begin(),nums.end());
        int p = nums[0]*nums[1]*nums[n-1];
        return max(p,nums[n-1]*nums[n-2]*nums[n-3]);
    }
};

class Solution{
public:
    int maximumProduct(vector<int> &nums){
        int mx1 = INT_MIN,mx2 = INT_MIN,mx3 = INT_MIN;
        int mn1 = INT_MAX,mn2 = INT_MAX;

        for(int num : nums){
            //求最大的三个数的方式
            if(num > mx1){
                mx3 = mx2;mx2 = mx1;mx1 = num;
            }
            else if(num>mx2){
                mx3 = mx2;mx2 = num;
            }
            else if(num > mx3){
                mx3 = num;
            }


            //求最小的两个数的方式
            if(num < mn1){
                mn2 = mn1;mn1 = num;
            }
            else if(num < mn2){
                mn2 = num;
            }
        }
        return max(mx1*mx2*mx3,mx1*mn1*mn2);
    }
};