问题描述:
Given an integer array nums, find three numbers whose product is maximum and return the maximum product.
给定任意数组,选三个值使其乘积最大
限定条件:
3 <= nums.length <= 10000 (保证至少三个数)
-1000 <= nums[i] <= 1000
思路:
1:如果只有三个数,那么就返回这三个数的乘积,别无其它选择
2:如果有超过三个数,我们才需要制定策略,当然要先排序
(1)如果最大值都小于等于零,最优乘积就是最大三个数乘积
例如(-8,-6,-6,-3,-2,-2,-1,0)
(2)如果最小值都大于等于零,最优乘积就是最大三个数乘积
例如(0,2,3,4,5,8,8,9,9)
(3)其它:即超过三个数且正负数混合,我们通过一定策略可以保证乘积非负。无非以下两种情况求较大值:(最大三个)或(最小两个加最大一个)的较大值。原理如下:我们可以这样想,从排好序的数组左侧(即最小值一侧)选几个数可以使乘积最大?选0个,当然可以,如果最大值的绝对值够大;选1个,不会出现这种情况,因为若这个数为正,则它不够大,若这个数为负,它只贡献了一个负号;选2个,可以,如果这两个数的绝对值够大;选3个,不会出现这种情况,道理同上。
代码如下:
class Solution {
public int maximumProduct(int[] nums) {
int last = nums.length - 1;
//case 0: when there are only 3 nums, then there is no choice
if (last==2) return nums[last]*nums[last-1]*nums[last-2];
//otherwise, we can sort the array to choose the best strategy
Arrays.sort(nums);
//case 1 and 2: when all nums are nonnegative or when all nums are nonpositive, product = product of largest 3
if ((nums[last]<=0)||(nums[0]>=0)) return nums[last]*nums[last-1]*nums[last-2];
//case 2: all others case(mix of negative and positive and >3 nums) we can guarantee a nonnegative product
//there are two possible ways we grab numbers to get the maximum product:
//(grab the largest 3) or (grab the smallest 2 and the largest 1), no other possibilities
else{
return Math.max(nums[last]*nums[last-1]*nums[last-2], nums[0]*nums[1]*nums[last]);
}
}
}
时间复杂度:O(nlogn)