# 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

```cpp
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

```cpp
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.

```cpp
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);
    }
};
```


---

# Agent Instructions: Querying This Documentation

If you need additional information that is not directly available in this page, you can query the documentation dynamically by asking a question.

Perform an HTTP GET request on the current page URL with the `ask` query parameter:

```
GET https://twchen.gitbook.io/leetcode/array/untitled.md?ask=<question>
```

The question should be specific, self-contained, and written in natural language.
The response will contain a direct answer to the question and relevant excerpts and sources from the documentation.

Use this mechanism when the answer is not explicitly present in the current page, you need clarification or additional context, or you want to retrieve related documentation sections.