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

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[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')
    
  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[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])
    
  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[0] * s[1])
    
  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
    

Leave a Reply

Fill in your details below or click an icon to log in:

WordPress.com Logo

You are commenting using your WordPress.com account. Log Out / Change )

Twitter picture

You are commenting using your Twitter account. Log Out / Change )

Facebook photo

You are commenting using your Facebook account. Log Out / Change )

Google+ photo

You are commenting using your Google+ account. Log Out / Change )

Connecting to %s

%d bloggers like this: