This problem could have been easily solved by taking the product of the three largest number if all the numbers were positive. But if you look at the constraints closely, the numbers can be negative as well. Let’s consider some cases:
- All numbers >=0: Maximum product is product of largest three numbers (eg: 432 in [4,3,2,1])
- All numbers <= 0: Maximum product is product of largest three numbers (eg: -1-2-3 in [-4,-3,-2,-1])
- Some numbers are negative and some are positive. Let’s consider some examples: ``` Example 1: [-4, -3, -2, 4, 5, 6] Here, maximum product = product of three largest numbers = 456
Example 2: [-4, -3, -2, 1, 2, 3] Here, product of three largest numbers = 123 = 6 But if we take the two smallest numbers (-4 and -3) and multiply with the largest number (+3), we will get the largest product = -4-33 = 36
Example 3: [-4, -3, -2, 1, 2] Again, largest product = -4-22
Hence, the maximum product of three numbers will be either product of the three largest numbers or product of largest number and two smallest numbers. So let us sort the array and return the maximum product amongst these.
int maximumProduct(vector
return max(nums[0]*nums[1]*nums[size-1], nums[size-1]*nums[size-2]*nums[size-3]); } ``` Time Complexity O(n*log(n)) Space Complexity O(1)