1. Sort the array (say arr) (O(nlgn)
2. Find the position of 0 in the array. The left of the array would be all -ve
and right of the array is all positive. Say zi is the position of zero, so
indices [0, zi) are all -ve and (zi, n-1] are all +ve. (O(lgn). If 0 is not
there in the array, we can still find its position, say it is b/w ith and
(i+1)th index. Then the -ve array would be with indices [0, i], and +ve array
would be (i, n-1].
3a. if(zi == n-1) // arr contains -ve elements only
return arr[0]*arr[1]*arr[2];
3b. if(zi == 0) // arr contains +ve elements only
return arr[n-1]*arr[n-2]*arr[n-3];
3c. return max{arr[n-1]*arr[n-2]*arr[n-3], arr[n-1]*arr[zi-1]*arr[zi-2]};
Only other cases remaining are boundry conditions, for e.g. if -ve array size
is 1, or when +ve array size is < 3.
So seems doable in O(nlgn + lgn).
________________________________
From: SP Praveen <[email protected]>
To: Algorithm Geeks <[email protected]>
Sent: Sunday, 13 September, 2009 7:04:37 PM
Subject: [algogeeks] max product of any three nos in an array of signed integers
Given an array of integers (signed integers), find three numbers in
that array which form the maximum product.
Now, send attachments up to 25MB with Yahoo! India Mail. Learn how.
http://in.overview.mail.yahoo.com/photos
--~--~---------~--~----~------------~-------~--~----~
You received this message because you are subscribed to the Google Groups
"Algorithm Geeks" group.
To post to this group, send email to [email protected]
To unsubscribe from this group, send email to
[email protected]
For more options, visit this group at http://groups.google.com/group/algogeeks
-~----------~----~----~----~------~----~------~--~---
