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.
分析
本题需要求数组中3个数相乘的最大值，数有正有负，说明需要考虑有负数的情况下两个负数相乘得正的情况。
那么乘积最大时，有哪些情况呢？
- 都是正数（包括0），最大的3个数相乘积最大
- 都是负数，最大的3个数相乘积最大
- 有正数也有负数，负数至少2个，那么最大正数与最小两个负数的乘积最大
- 有正数也有负数，负数1个，那么最大的3个正数相乘积最大
因此，我们只需要知道数组中最大的3个数和最小的2个数即可，然后取最大3个数的乘积与最大数和最小两个数乘积的较大者即可。遍历一次数组即可求得。
code
class Solution {
public int maximumProduct(int[] nums) {
int max1, max2, max3, min1, min2;
max1 = max2 = max3 = Integer.MIN_VALUE;
min1 = min2 = Integer.MAX_VALUE;
for (int n : nums) {
if (n > max1) {
max3 = max2;
max2 = max1;
max1 = n;
}
else if (n > max2) {
max3 = max2;
max2 = n;
}
else if (n > max3) {
max3 = n;
}
if (n < min1) {
min2 = min1;
min1 = n;
}
else if (n < min2) {
min2 = n;
}
}
return Math.max(max1*max2*max3, max1*min1*min2);
}
}
