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 <praveen.sel...@gmail.com> To: Algorithm Geeks <algogeeks@googlegroups.com> 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 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 -~----------~----~----~----~------~----~------~--~---