Maximum Product Of Three
September 27, 2016
Today’s exercise comes from the end-of-chapter exercises in the sorting chapter of a programming textbook:
Write a program that finds the maximum product of three numbers in a given array of integers.
Your task is to write the desired program. When you are finished, you are welcome to read or run a suggested solution, or to post your own solution or discuss the exercise in the comments below.
Programming Praxis 
In Python. These 2 functions pass all PP tests. If there are at least 3 numbers there is only one rule: use either the 3 largest numbers or the largest number and the 2 smallest numbers. I test, if the largest number is negative, but this is not really needed.
def maxp1(seq): if len(seq) < 3: raise ValueError("sequence should have at least 3 numbers") s = sorted(seq) p1 = s[-1] * s[-2] * s[-3] if s[-1] <= 0: return p1 return max(p1, s[0] * s[1] * s[-1]) def maxp2(seq): 'using 2 heaps to keep the 2 lowest numbers , and the 3 highest' if len(seq) < 3: raise ValueError("sequence should have at least 3 numbers") L, H = [], [] # heaps for 2 lowest and 3 highest values for i, e in enumerate(seq): if i < 2: heappush(L, -e) elif -e > L[0]: heapreplace(L, -e) if i < 3: heappush(H, e) elif e > H[0]: heapreplace(H, e) p1 = H[0] * H[1] * H[2] if max(H) <= 0: return p1 return max(p1, max(H) * L[0] * L[1])A shorter version of maxp2.
def maxp2(seq): if len(seq) < 3: raise ValueError("sequence should have at least 3 numbers") H = heapq.nlargest(3, seq) p1 = H[0] * H[1] * H[2] if max(H) <= 0: return p1 L = heapq.nsmallest(2, seq) return max(p1, max(H) * L[0] * L[1])Implemented in Julia. Although the problem seems straight-forward, a brute-force approach might not be the best way to go, since there may be 0s in the given Array. Here is my solution, that takes care of this point. Of course, this whole thing could be implemented in 2 loops, but loops in this language are so fast that for most cases it won’t really much difference. Also, in problems like this I minimize the development time.
function main(x::Array{Int64, 1})
nx = length(x)
if nx < 3
println("Array is too short! Please provide at least 3 integers.")
return NaN
elseif nx == 3
return prod(x)
else
z = x[x .!= 0] # get rid of all the 0s]
M = -maximum(z)
n = length(z)
for i = 1:(n-2)
for j = (i+1):(n-1)
for k = (j+1):n
M = max(M, z[i]*z[j]*z[k])
end
end
end
return M
end
end
in PHP
function maximum($A) {
$f=1;
arsort($A);
$b=array_values($A);
for($i=0; $i<3; $i++) {
$f=$f*$b[$i];
}
return print_r($f);
}
[…] studied that problem in a previous exercise, where unfortunately we got it wrong. Here is the suggested solution from that […]