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:

1. The length of the given array will be in range [3,104] and all elements are in the range [-1000, 1000].
2. Multiplication of any three numbers in the input won't exceed the range of 32-bit signed integer.

 

这个题目就是需要注意负数的情况即可, 我们如果用排序的话, 比较max(nums[0]*nums[1]*nums[-1], nums[-1]*nums[-2]*nums[-3])即可. T: O(nlgn)

要T: O(n) 的话就需要得到min1, min2, max1, max2, max3同理比较max(min1 * min2 * max1, max1 * max2 * max3)即可.

 

Code

1) T: O(nlgn)

class Solution:    def maxProduct3nums(self, nums):        nums.sort()        return max(nums[0]*nums[1]*nums[-1], nums[-1]*nums[-2]*nums[-3])

 

2) T: O(n)

class Solution:    def maxProduct3nums(self, nums):        ans = [1001]*2 + [-1001]*3  # min1, min2, max1, max2, max3        for num in nums:            if num > ans[-1]:                ans[-1], ans[-2], ans[-3] = num, ans[-1], ans[-2]            elif num > ans[-2]:                ans[-2], ans[-3] = num, ans[-2]            elif num > ans[-3]:                ans[-3] = num            if num < ans[0]:                ans[0], ans[1] = num, ans[0]            elif num < ans[1]:                ans[1] = num        return max(ans[0]*ans[1]*ans[-1], ans[-1]*ans[-2]*ans[-3])

 

 

---