Maximum Product of Three Numbers

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.

Github: code.dennyzhang.com

Credits To: leetcode.com

Leave me comments, if you have better ways to solve.

## Blog link: https://code.dennyzhang.com/maximum-product-of-three-numbers ## Basic Ideas: The biggest number will definitley exists in the target combination. ## Why? b>c and a>0, then b*a>c*a ## Let's say (p1, p2, p3) is the target. And the biggest number p4 is not in the combination. ## 1. If there is one positive number inside the target. Let's say p3 is positive. Then p3 must be p4 ## Otherwise p4*(p1*p2) > p3*(p1*p2) ## 2. If all negative, the max is also negative. Let's say p4 not in the target ## p1*p2 > 0 and p4>p3, then p4*(p1*p2) > p3*(p1*p2) ## 3. If there is 0 inside the target. ## If the array has no positive, 0 is the max. p4=0 ## If the array has only 1 positive, then the array won't have more than 2 negative. ## Otherwise 0 won't be chosen. So the array only have 3 elements. The max will be chosen ## If the array has 2 positives. The array won't have more than 2 negative. ## Let's say it has only 0 negative, then the array would be 0 ++. Tha max will be chosen. ## Suppose it has 1 negative, the array would be: - 0 + + ## If we choose: max([1st_min, 2nd_min, 1st_max], [2nd_max, 3rd_max, 1st_max]), ## we will get the maxmium. ## This time we don't need to choose the max, but choosing the max will also work. ## If the array has 3 positives. 0 won't be chosen. So invalid. ## ## ## As a conclusion, the max number exists in the target combination. ## ## Now p3=p4, and the problem drops to choose 2 elements. ## 1. If there are two positive in p1, p2, we can simply choose the next 2 biggest numbers. ## [2nd_max, 3rd_max]. And they are gurantee to be positive. ## 2. If there are two negative in p1, p2, we should choose the 2 smallest numbers. ## [1st_min, 2nd_min] ## 3. If there are only one neagive and one positive. p3 must be positive. So the result must be negative ## Let's say p1<0, p2>0, p3>0. This means the array will only have 2 positive. ## So p2 is the next biggest number. ## Then p1 is the biggest negative, so p1 is the 3rd biggest nubmer. ## [2nd_max, 3rd_max] ## 4. If there is 0 in the target. Let's say p3 is 0, it doesn't matter what elements we choose for p1 and p2 ## Let's say p1 or p2 is 0. Then 0 would be one of these: the 2nd max, or the 3rd max ## Why? there would another 2 positive. Then we can get a positive product, instead of 0. ## So one of [2nd_max, 3rd_max] is 0. ## If we choose [2nd_max, 3rd_max, 1st_max] as our result, we will get 0. Still the biggest. ## [2nd_max, 3rd_max] ## ## As a conclusion, [p1, p2] == [1st_min, 2nd_min] or [2nd_max, 3rd_max] ## ## Watch out: you might have negative or 0 ## ## Complexity: O(n*log(n)), O(1) class Solution(object): def maximumProduct(self, nums): """ :type nums: List[int] :rtype: int """ length = len(nums) if length < 3: return None nums.sort() return max(nums[-1]*nums[-2]*nums[-3], nums[-1]*nums[0]*nums[1])