I need to write a program to find the Max product of three numbers for a given array of size N. Is there any effective algorithm for this? I just need to know the algorithm steps. Non of algorithms that i thought works for all the test cases. Thanks! FYI Array may contains +ve, -ve, or zero elements)
+7
A:
Find the three largest numbers in the array (n1, n2, n3) and the two smallest numbers (m1, m2).
The answer is either n1 x n2 x n3 or n1 x m1 x m2
mobrule
2010-02-02 20:31:23
Why isn't it just n1 x n2 x n3?
Ink-Jet
2010-02-02 20:35:39
@Ink-Jet because m1 and m2 might be large negative numbers
mobrule
2010-02-02 20:37:02
Excluding 0, of course :)
BlueRaja - Danny Pflughoeft
2010-02-02 20:40:43
@BlueRaja - exclude 0 from what?
mobrule
2010-02-02 20:49:43
@mobrule Ah, yes. That makes a lot of sense. Thanks! +1 for you.
Ink-Jet
2010-02-02 20:53:04
One other case not covered in this solution is if all the numbers are negative. Then the maximum product is the product of those three numbers with the SMALLEST modulus.
woodchips
2010-02-02 20:57:57
@woodchips: Which are the three largest numbers in the array.
280Z28
2010-02-02 21:03:07
A:
Given an array of list = (n1, n2, n3...). You can do this in 3 passes.
Let a1 = max (|n_i|)
Let a2 = max (|n_i|) where n_i != a1
Now a1*a2 is either positive, negative or zero. If zero then there are many solutions; pick any n_i from the rest of the numbers. If a1*a2 > 0 then pick the largest positive number otherwise smallest negative number. More succinctly, you can just make one pass through the rest of the list:
Let max_product = max (a1*a2*n_i) where n_i != a1 or a2
Ray
2010-02-02 21:38:18