Maximum Product Of Three, Revisited
June 30, 2017
Today’s exercise is simply stated:
Write a program that finds the maximum product of three numbers in a given array of integers.
We studied that problem in a previous exercise, where unfortunately we got it wrong. Here is the suggested solution from that exercise:
(define (max-prod-three xs)
(let ((len (length xs)) (xs (sort < xs)))
(cond ((< len 3) (error 'max-prod-three "insufficient input"))
((= len 3) (apply * xs))
((positive? (car xs))
(apply * (take 3 (reverse xs))))
((negative? (last xs))
(apply * (take 3 (reverse xs))))
((and (negative? (car xs)) (positive? (cadr xs)))
(apply * (take 3 (reverse xs))))
((and (negative? (cadr xs))
(negative? (caddr (reverse xs))))
(* (car xs) (cadr xs) (last xs)))
((and (negative? (cadr xs))
(positive? (caddr (reverse xs))))
(max (apply * (take 3 (reverse xs)))
(* (car xs) (cadr xs) (last xs))))
(else (error 'max-prod-three "missed case")))))
Your task is to write a correct program that finds the maximum product of three numbers in a given array of integers; you might start by figuring out what is wrong with the previous 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 
It’s the product of the lowest two and highest, or the product of the highest three, no need to test signs. This Python implementation returns the actual numbers. It assumes there are at least three numbers.
from functools import reduce from operator import mul def prod(xs): return reduce(mul, xs) def sweet(xs): xs = sorted(xs) # essential lo = (xs[0], xs[1], xs[-1]) hi = (xs[-3], xs[-2], xs[-1]) return max((lo, hi), key = prod)Test code examines all combinations of three numbers in random samples. Sorting makes for nicer output and for easier testing that the result is the same as with the actual solution. Products are. Actual numbers sometimes differ.
from itertools import combinations from random import randint def brute(xs): xs = sorted(xs) # nice return max(combinations(xs, 3), key = prod) for sample in ([randint(-4,4) for k in range(5)] for k in range(10)): bmax, smax = brute(sample), sweet(sample) print('PASS' if prod(bmax) == prod(smax) else 'FAIL', 'SAME' if bmax == smax else 'DIFF', bmax, smax, sep = '\t')In Python. Same solution as used last time.
def bf(seq): return max(a*b*c for a, b, c in combinations(seq, 3)) def maxp1(seq): s = sorted(seq) return s[-1] * max(s[-2] * s[-3], s[0] * s[1]) def maxp2(seq): H = heapq.nlargest(3, seq) L = heapq.nsmallest(2, seq) return max(H[0] * H[1] * H[2], max(H) * L[0] * L[1])Thus in Scheme, given a take, with the arguments to sort in another order.
(define (max-prod-three xs) (let* ((xs (sort xs <)) (rs (reverse xs))) (max (apply * (take 3 rs)) (apply * (append (take 2 xs) (take 1 rs))))))Passes (in Guile) the test copied from the site where the code can be run.
(Apologies for the dup, checking if the indentation might survive as I meant it.)
(define (max-prod-three xs) (let* ((xs (sort xs <)) (rs (reverse xs))) (max (apply * (take 3 rs)) (apply * (append (take 2 xs) (take 1 rs))))))Implementation in Julia. No assumption whatsoever, plus no dependencies (as usual). Kernel version: 0.4.5
function main{T <: Integer}(x::Array{T, 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
ind = (x .!= 0) # indexes of 0s
nz = sum(ind)
z = x[ind] # get rid of all the 0s
n = length(z)
if n < 3; return 0; end
M = typemin(eltype(z)) # start somewhere super low
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
if (M 0)
return 0
else
return M
end
end
end
@Zack, whatever you are doing is not working. Try the sourcecode tags: a line like (sourcecode lang=”text”) before your code and (/sourcecode) after your code, except with square brackets. It will preserve indentation, and it will preserve less-than and greater-than signs, and some other things. It will also do syntax highlighting for supported languages but Julia is not one of those.
See “HOWTO: Posting source code” in the red bar on top of the page. (There’s also Praxis’s sed script method there.)
(Incidentally, no need to handle zeroes specially. And the correct answer can be negative. You should trust your loops :)
maxp1 in my last post is wrong. This should work
def maxp1(seq): s = sorted(seq) mm = min if s[-1] < 0 else max return s[-1] * mm(s[-2] * s[-3], s[0] * s[1])@Jussi. Thank you for your feedback and the tips. I’ll be sure to format my code next time, based on these tags.
I address the zeros in order to make the code more efficient. If the non-zero elements are less than 3, there is no point trying anything else since the maximum product is going to be 0.
I do trust the loops, esp. in this language, where they are very efficient. I’m not sure why this comment is relevant at all.
The last part of the code didn’t copy correctly for some reason. Here it is again:
sourcecode lang=”text”
if (M 0)
return 0
else
return M
end
/sourcecode
This basically ensures that if there are zeros present, the end result would be 0, rather than a negative number. The latter is possible only if all the elements of the array are non-zero.
Perhaps this would be a better way to accurately share code:
https://app.box.com/s/toyycilmubrvgz83vzlyred31jc84pyg
@Zack, the removal of zeroes looks like a premature optimization to me. You don’t know that it helps much, or at all. It makes your code about twice as long and complex as it otherwise is. And your algorithm is still cubic in the length of the array.
Maybe if you knew that there are lots of zeroes for some reason. But that information is not given. In sorting-based solutions they don’t matter even then.
You need to type the sourcecode tags in square brackets (the same characters you use in indexing Julia arrays) and the doublequotes need to be straight ASCII doublequotes. Just try again.
This is your solution without the special handling of zeroes.
function main{T <: Integer}(x::Array{T, 1}) z = x # let zeroes be n = length(z) n < 3 && throw(DomainError()) M = typemin(eltype(z)) # start somewhere super low 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 endHere’s a test output. I’m only sorting the array for nicer display. Hm. Should only have sorted for output then. There’s always something :)
for k = 1:5 a = sort(rand(-4:4, 7)) println(main(a), '\t', a) end