Teaching Kids Programming: Videos on Data Structures and Algorithms
Given a array of numbers (more than 3 elements), not necessarily sorted, find out the max product of 3 numbers. The numbers could be negative.
Max Product of 3 Numbers
First, we need to sort the array either in ascending or non-ascending order. This takes O(NLogN) time i.e. N is the number of elements in the array. Since the array could contain negative numbers, and double negative makes a positive product. We also need to check the produce between the largest number and the two smallest numbers.
def maxProduct(nums):
nums.sort()
return max(nums[-1] * nums[-2] * nums[-3], nums[0] * nums[1] * nums[-1])
We can also store the max 3 numbers, the min two numbers in O(N) time.
Max product of either two numbers or three numbers:
- Teaching Kids Programming – Max Product of Two Numbers
- Teaching Kids Programming – Compute the Max Product of 3 Numbers in the Array
- Compute the Maximum Product of Three Numbers in an Array
- Algorithm to Compute the Largest Triple Products from Array
–EOF (The Ultimate Computing & Technology Blog) —
Last Post: A Concise Python Function to Check Subsequence using Iterator
Next Post: Teaching Kids Programming - Confusing Number Validation Algorithm