forked from wuduhren/leetcode-python
-
Notifications
You must be signed in to change notification settings - Fork 0
Expand file tree
/
Copy pathmaximum-product-of-three-numbers.py
More file actions
38 lines (32 loc) · 1.09 KB
/
maximum-product-of-three-numbers.py
File metadata and controls
38 lines (32 loc) · 1.09 KB
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
"""
if we sort the array, the max would be the product 3 numbers on the right.
but if there are negative numbers, it could also be possible that
two negative numbers lying at the left extreme end could also contribute to lead to a larger product.
thus, after sorting, either
max1 * max2 * max3
max1 * min1 * min2
so our gaol will be to find the max 3 numbers and min 2 numbers in the array
"""
class Solution(object):
def maximumProduct(self, nums):
min1 = float('inf') #smallest
min2 = float('inf') #second smallest
max1 = float('-inf') #largest
max2 = float('-inf') #second largest
max3 = float('-inf') #third largest
for n in nums:
if n<=min1:
min2 = min1
min1 = n
elif n<=min2:
min2 = n
if n>=max1:
max3 = max2
max2 = max1
max1 = n
elif n>=max2:
max3 = max2
max2 = n
elif n>=max3:
max3 = n
return max(min1*min2*max1, max1*max2*max3)