05 August 2008
Given an integer array, find three numbers whose product is maximum and output the maximum product.
Example 1:
1
2
Input: [1,2,3]
Output: 6
Example 2:
1
2
Input: [1,2,3,4]
Output: 24
Note:
这道题是在数组中找到三个数相乘的乘积为最大，限制了条件，三个数的乘积不会超过Integer的范围，这道题需要考虑的地方就是负数，1）如果全是正数，那没什么好说的直接最大的三个数相乘即可，如果数组里面全是负数，那么三个数相乘就应该是绝对值最小的三个数，也是三个最大的数相乘；2）如果有正数有负数，那么就应该是最大的正数和最小的两个负数相乘；注意想想这道题可将0划到正数那一伙并不会影响结果，所以可以先排序在分别算出来两种情况的乘积然后比较即可；如果不想排序，那么就先循环一遍找到三个最大的数，和两个最小的数，最后比较看二选一哪种情况大，返回即可。
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
class Solution {
public int maximumProduct(int[] nums) {
if (nums.length < 3) {
return 0;
}
int max1 = Integer.MIN_VALUE, max2 = Integer.MIN_VALUE, max3 = Integer.MIN_VALUE;
int min1 = Integer.MAX_VALUE, min2 = Integer.MAX_VALUE;
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 Math.max(max1 * max2 * max3, max1 * min1 * min2);
}
}