## 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.

Advertisements

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.

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.

In Python. Same solution as used last time.

Thus in Scheme, given a take, with the arguments to sort in another order.

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.)

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

@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.

Here’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 :)