Maximum Product of Three Numbers
Problem
Find three numbers in the array whose product is maximum.
nums = [-100,-98,-1,2,3,4]39200def maximum_product(nums):
nums = sorted(nums)
return max(nums[-1] * nums[-2] * nums[-3], nums[0] * nums[1] * nums[-1])function maximumProduct(nums) {
nums.sort((a, b) => a - b); const n = nums.length;
return Math.max(nums[n-1]*nums[n-2]*nums[n-3], nums[0]*nums[1]*nums[n-1]);
}int maximumProduct(int[] nums) {
Arrays.sort(nums); int n = nums.length;
return Math.max(nums[n-1]*nums[n-2]*nums[n-3], nums[0]*nums[1]*nums[n-1]);
}int maximumProduct(vector& nums) {
sort(nums.begin(), nums.end()); int n = nums.size();
return max(nums[n-1]*nums[n-2]*nums[n-3], nums[0]*nums[1]*nums[n-1]);
} Explanation
The biggest product of three numbers comes from just two possibilities, so we sort the array and compare them. There is no need to check every triple.
The first candidate is the product of the three largest numbers, nums[n-1] * nums[n-2] * nums[n-3]. That is the obvious choice when everything is positive.
The second candidate handles negatives: two negative numbers multiply to a positive, so the two smallest values times the largest, nums[0] * nums[1] * nums[n-1], can win if those negatives are large in magnitude.
After sorting, both candidates are read straight off the ends of the array, and we return whichever is bigger with max(...).
Example: [-100,-98,-1,2,3,4] sorts to itself. Top three give 2*3*4 = 24, while two smallest times largest give (-100)*(-98)*4 = 39200, so the answer is 39200.