Maximum Product Of Three

September 27, 2016

This is harder than it looks; the problem is that the input may contain both positive and negative numbers. It took me longer than I care to admit and much experimentation to come up with the following solution:

  • If the input has less than three numbers, the problem is ill-formed.
  • If the input has exactly three numbers, the result is their product.
  • If the input has four or more numbers, all of them positive, the result is the product of the three largest numbers.
  • If the input has four or more numbers, all of them negative, the result is the product of the three largest numbers (closest to zero).
  • If the input has four or more numbers, withexactly one negative number, the result is the product of the three largest numbers.
  • If the input has four or more numbers, at least two of them negative and one or two of them positive, the result is the product of the two largest negative numbers (farthest from zero) and the largest positive number.
  • If the input has five or more numbers, at least two of them negative and at least three of them positive, the result is the larger of the product of the three largest positive numbers or the two largest negative numbers (farthest from zero) and the largest positive number.

I think that covers all the cases. Here is the resulting function:

(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")))))

I left the else clause in the code due to a gnawing sense of insecurity that I had missed a case; I don’t think so, but I prefer to have a warning message rather than some random result. Here is my test suite:

> (define (test-max-prod-three)
    (assert (+ 1 1) 3) ; testing assert
    (assert (max-prod-three '(1 2 3))           6)
    (assert (max-prod-three '(-1 -2 -3))       -6)
    (assert (max-prod-three '(1 2 3 4))        24)
    (assert (max-prod-three '(-1 2 3 4))       24)
    (assert (max-prod-three '(1 -2 3 4))       12)
    (assert (max-prod-three '(1 2 -3 4))        8)
    (assert (max-prod-three '(1 2 3 -4))        6)
    (assert (max-prod-three '(-1 -2 -3 -4))    -6)
    (assert (max-prod-three '(1 -2 -3 -4))     12)
    (assert (max-prod-three '(-1 2 -3 -4))     24)
    (assert (max-prod-three '(-1 -2 3 -4))     24)
    (assert (max-prod-three '(-1 -2 -3 4))     24)
    (assert (max-prod-three '(1 2 3 4 5))      60)
    (assert (max-prod-three '(-1 -2 -3 -4 -5)) -6)
    (assert (max-prod-three '(1 2 -3 -4 -5))   40)
    (assert (max-prod-three '(-1 -2 3 4 5))    60)
    (assert (max-prod-three '(-1 -2 -3 4 5))   30)
    (assert (max-prod-three '(1 -2 3 -4 5))    40)
    (assert (max-prod-three '(-1 2 -3 4 -5))   60)
    (assert (max-prod-three '(1 2 3 4 -5))     24)
    (assert (max-prod-three '(-1 2 3 4 5))     60)
    (assert (max-prod-three '(-1 -2 -3 -4 5))  60)
    (assert (max-prod-three '(1 -2 -3 -4 -5))  20)
    (assert (max-prod-three '(1 2 3 4 5 6 7)) 210))
failed assertion:
(+ 1 1)
expected: 3
returned: 2

As always, no news is good news. You can run the program at http://ideone.com/plGB25, where you will also see the take and last functions and the assert macro.

Pages: 1 2

5 Responses to “Maximum Product Of Three”

  1. Paul said

    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])
    
  2. Paul said

    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])
    
    
    
  3. Zack said

    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

  4. Aquiles Peña said

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

    }

  5. […] studied that problem in a previous exercise, where unfortunately we got it wrong. Here is the suggested solution from that […]

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 )

Google photo

You are commenting using your Google 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 )

Connecting to %s

%d bloggers like this: