Maximum Product of Three Numbers

Description

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:

1. The length of the given array will be in range [3, $10^4$] and all elements are in the range [-1000, 1000].

2. Multiplication of any three numbers in the input won't exceed the range of 32-bit signed integer.

Solutions

My solution 1

class Solution {
public:
    int maximumProduct(vector<int>& nums) {
        sort(nums.begin(), nums.end());
        vector<int> pos;
        vector<int> neg;
        for(int num : nums){
            if(num < 0)
                neg.push_back(num);
            else
                pos.push_back(num);
        }
        // 3 non-negative numbers
        int p1 = pos.size() < 3 ? INT_MIN : (pos.end()[-1] * pos.end()[-2] * pos.end()[-3]);
        // 2 non-negative numbers and 1 negative number
        int p2 = (pos.size() < 2 || neg.size() < 1) ? INT_MIN : (neg.back() * pos[0] * pos[1]);
        // 1 non-negative number and 2 negative numbers
        int p3 = (pos.size() < 1 || neg.size() < 2) ? INT_MIN : (pos.back() * neg[0] * neg[1]);
        // 3 negative numbers
        int p4 = neg.size() < 3 ? INT_MIN : (neg.end()[-1] * neg.end()[-2] * neg.end()[-3]);
        return max(max(p1, p2), max(p3, p4));
    }
};

My solution 2

class Solution {
public:
    int maximumProduct(vector<int>& nums) {
        sort(nums.begin(), nums.end());
        // 3 positives
        int p1 = nums.end()[-1] * nums.end()[-2] * nums.end()[-3];
        // 2 negatives and 1 positive
        int p2 = nums[0] * nums[1] * nums.back();
        return max(p1, p2);
    }
};

A better solution

Do not sort the array, just find the biggest 3 and smallest 2 numbers.

class Solution {
public:
    int maximumProduct(vector<int>& nums) {
        int max1 = INT_MIN, max2 = INT_MIN, max3 = INT_MIN, min1 = INT_MAX, min2 = INT_MAX;
        for(int num : nums){
            if(num > max1){
                max3 = max2;
                max2 = max1;
                max1 = num;
            }else if(num > max2){
                max3 = max2;
                max2 = num;
            }else if(num > max3){
                max3 = num;
            }
            if(num < min1){
                min2 = min1;
                min1 = num;
            }else if(num < min2){
                min2 = num;
            }
        }
        return max(max1 * max2 * max3, min1 * min2 * max1);
    }
};