This one is better than what I suggested before. Doable in O(n)!
On Sep 13, 10:10 pm, Dave <dave_and_da...@juno.com> wrote:
> The following assumest that n >= 5. Find the 3 largest positive
> numbers and the two largest-in-magnitude negative numbers (i.e., the
> two smallest signed numbers).
>
> If there are not two negative numbers, the 3 largest positive numbers
> are the answer.
>
> Otherwise, if there are only one or two positive numbers, the largest
> positive number and the two largest-in-magnitude negative numbers are
> the answer.
>
> Otherwise, compare the product of the three largest positive numbers
> with the product of the largest positive number and the two largest-in-
> magnitude negative numbers. The answer is whichever set produces the
> largest product.
>
> If the product of the answer set is zero, the answer will not be
> uniquely determined.
>
> This can be done in O(n) time and O(1) extra space.
>
> Dave
>
> On Sep 13, 8:34 am, SP Praveen <praveen.sel...@gmail.com> wrote:
>
> > Given an array of integers (signed integers), find three numbers in
> > that array which form the maximum product.
Try the new Yahoo! India Homepage. Click here. http://in.yahoo.com/trynew
--~--~---------~--~----~------------~-------~--~----~
You received this message because you are subscribed to the Google Groups
"Algorithm Geeks" group.
To post to this group, send email to algogeeks@googlegroups.com
To unsubscribe from this group, send email to
algogeeks+unsubscr...@googlegroups.com
For more options, visit this group at http://groups.google.com/group/algogeeks
-~----------~----~----~----~------~----~------~--~---
