This notebook was prepared by Donne Martin. Source and license info is on GitHub.
Use three loops and multiple each numbers.
Complexity:
Sort the list, multiply the last three elements.
Complexity:
0 1 2 3 4 5 [5, -2, 3, 1, -1, 4] -> 60 max_prod_of_three = -30 max_prod_of_two = -10 max_num = 5 min_prod_of_two = -10 min_num = -2 0 1 2 3 4 5 [5, -2, 3, 1, -1, 4] -> 60 ^ max_prod_of_three = -30 max_prod_of_two = 15 max_num = 5 min_prod_of_two = -10 min_num = -2 0 1 2 3 4 5 [5, -2, 3, 1, -1, 4] -> 60 ^ max_prod_of_three = 15 max_prod_of_two = 15 max_num = 5 min_prod_of_two = -10 min_num = -2 0 1 2 3 4 5 [5, -2, 3, 1, -1, 4] -> 60 ^ max_prod_of_three = 15 max_prod_of_two = 15 max_num = 5 min_prod_of_two = -10 min_num = -2 0 1 2 3 4 5 [5, -2, 3, 1, -1, 4] -> 60 ^ max_prod_of_three = 60 max_prod_of_two = 15 max_num = 5 min_prod_of_two = -10 min_num = -2
Complexity:
class Solution(object):
def max_prod_three_nlogn(self, array):
if array is None:
raise TypeError('array cannot be None')
if len(array) < 3:
raise ValueError('array must have 3 or more ints')
array.sort()
product = 1
for item in array[-3:]:
product *= item
return product
def max_prod_three(self, array):
if array is None:
raise TypeError('array cannot be None')
if len(array) < 3:
raise ValueError('array must have 3 or more ints')
curr_max_prod_three = array[0] * array[1] * array[2]
max_prod_two = array[0] * array[1]
min_prod_two = array[0] * array[1]
max_num = max(array[0], array[1])
min_num = min(array[0], array[1])
for i in range(2, len(array)):
curr_max_prod_three = max(curr_max_prod_three,
max_prod_two * array[i],
min_prod_two * array[i])
max_prod_two = max(max_prod_two,
max_num * array[i],
min_num * array[i])
min_prod_two = min(min_prod_two,
max_num * array[i],
min_num * array[i])
max_num = max(max_num, array[i])
min_num = min(min_num, array[i])
return curr_max_prod_three
%%writefile test_prod_three.py
import unittest
class TestProdThree(unittest.TestCase):
def test_prod_three(self):
solution = Solution()
self.assertRaises(TypeError, solution.max_prod_three, None)
self.assertRaises(ValueError, solution.max_prod_three, [1, 2])
self.assertEqual(solution.max_prod_three([5, -2, 3]), -30)
self.assertEqual(solution.max_prod_three([5, -2, 3, 1, -1, 4]), 60)
print('Success: test_prod_three')
def main():
test = TestProdThree()
test.test_prod_three()
if __name__ == '__main__':
main()
Overwriting test_prod_three.py
%run -i test_prod_three.py
Success: test_prod_three