## Maximum Product Of Three, Revisited

### June 30, 2017

The error appears when trying to find the maximum product of three of the list `(0 1 2 3)`, which is 6. Here’s what our program does:

```> (max-prod-three '(0 1 2 3))
Exception in max-prod-three: missed case```

That case should be caught by the second `cond` clause, but isn’t; changing the test from `positive?` to `not (negative?` fixes the problem:

```(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))
((not (negative? (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))))
(* (car xs) (cadr xs) (last xs)))
(max (apply * (take 3 (reverse xs)))
(* (car xs) (cadr xs) (last xs))))
(else (error 'max-prod-three "missed case")))))```

And now everything works properly:

```> (max-prod-three '(0 1 2 3))
6```

We also add a new test case to the list in the previous exercise, which you will see at http://ideone.com/c9S7FL. This is a good lesson in how not to test your work.

Pages: 1 2

### 10 Responses to “Maximum Product Of Three, Revisited”

1. Jussi Piitulainen said

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, xs, 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')
```
2. Paul said

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 * s)

def maxp2(seq):
H = heapq.nlargest(3, seq)
L = heapq.nsmallest(2, seq)
return max(H * H * H, max(H) * L * L)
```
3. Jussi Piitulainen said

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.

4. Jussi Piitulainen said

(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))))))
```
5. Zack said

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

6. Jussi Piitulainen said

@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 :)

7. Paul said

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 * s)
```
8. Zack said

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

9. Zack said

Perhaps this would be a better way to accurately share code:
https://app.box.com/s/toyycilmubrvgz83vzlyred31jc84pyg

10. Jussi Piitulainen said

@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
end
```

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

```for k = 1:5
a = sort(rand(-4:4, 7))
println(main(a), '\t', a)
end
```