### 题目

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.

### 思路

[1,2,3,4,5,6,7,8,9]


[-6,-5,-4,-3,-2,-1,7,8,9]


[-7,-6,-5,-4,-3,-2,-1,8,9]


[-8,-7,-6,-5,-4,-3,-2,-1,9]


[-9,-8,-7,-6,-5,-4,-3,-2,-1]


### 先排序，$O(n\log_{}{n})$

#### 代码

class Solution {
public int maximumProduct(int[] nums) {
Arrays.sort(nums);
return Math.max(nums[0]*nums[1]*nums[nums.length-1], nums[nums.length-3]*nums[nums.length-2]*nums[nums.length-1]);
}
}


### 不排序，$O(n)$得到最大和最小的几个数

#### 代码

class Solution {
public int maximumProduct(int[] nums) {
int[] min = new int[]{Integer.MAX_VALUE, Integer.MAX_VALUE};
int[] max = new int[]{Integer.MIN_VALUE, Integer.MIN_VALUE, Integer.MIN_VALUE};
for (int num : nums) {
if (num < min[1]) {
min[1] = num;
if (num < min[0]) { exch(min,0,1); }
}
if (num > max[2]) {
max[2] = num;
if (num > max[1]) { exch(max,1,2); }
if (num > max[0]) { exch(max,0,1); }
}
}
return Math.max(min[0]*min[1]*max[0],max[2]*max[1]*max[0]);
}
public void exch(int[] nums, int x, int y) {
int temp = nums[x];
nums[x] = nums[y];
nums[y] = temp;
}
}