Finding highest product of three numbers

Question

Given an array of ints, arrayofints, find the highest product, Highestproduct, you can get from three of the integers. The input array of ints will always have at least three integers.

So I've popped three numbers from arrayofints and stuck them in highestproduct:

Highestproduct = arrayofints[:2] for item in arrayofints[3:]:     If min(Highestproduct) < item:         Highestproduct[highestproduct.index(min(Highestproduct))] = item 

If min of highestproduct less than item: Replace the lowest number with the current number.

This would end up with highest product, but apparently there is a better solution. What's wrong with my approach? Would my solution be O(n)?

Answer 1

Keep track of the two minimal elements and three maximal elements, the answer should be min1 * min2 * max1 or max1 * max2 * max3.

To get the maximum product of 3 ints we have to choose 3 maximum elements. However there is a catch that we can substitute 2 of the smallest of 3 max elements with the 2 min ints. If both smallest ints are negative their product is positive so min1 * min2 might be bigger than max2 * max3 (where max2 and max3 are 2 of the smallest of 3 max elements from the array).

This runs in O(n) time.