From: "Eric I." <rubytraining@...>
Date: 2007-01-02T01:40:05+09:00
Subject: Re: contest season (or something)

William James wrote:
> pat eyler wrote:
> >From the site:
> "You are given N integer numbers. Choose thee of them which give
> maximum product."
>
> I don't get it.  Isn't this the same as finding the 3 largest numbers?

Well, consider this list of numbers:

    5, 5, 10, -10, -10

The product of the three largest numbers (those closest to positive
infinity) is 250.  But the highest product is 1000 that you'd get from
10, -10, and -10.  Pairs of negative numbers become significant.

So the simplest algorithm would be along these lines:

    * sort the numbers
    * calculate the product of the three highest numbers
    * calculate the product of the one highest and the two lowest
    * compare those two products and choose the larger

Eric