Agreed finding the largest is O(n). Finding the largest k will be O(n log k). Just coz we don't have loops it doesn't mean the op is O(1). Product of largest 3 does not guarantee largest product! (Take for e.g. -10, 5, 0, -20, 8. The max product is 1600, not 0.
On Wed, Sep 16, 2009 at 2:48 AM, Prashant <prashant.r.k...@gmail.com> wrote: > hi all, > i think we can use kth smallest algorithm (from cormen book) to find three > largest numbers from given and multiplication of these number will leads to > max product..... > > time complexity will be 3*O(n) > 3->for finding three largest numbers > O(n)->time complexity of Kth Smallest algorithm > > On Wed, Sep 16, 2009 at 3:11 PM, manish bhatia <mb_mani...@yahoo.com>wrote: > >> >> 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. >> >> ------------------------------ >> Keep up with people you care about with Yahoo! India Mail. Learn >> how<http://in.rd.yahoo.com/tagline_galaxy_1/*http://in.overview.mail.yahoo.com/connectmore> >> . >> >> > > > -- > > Prashant Kulkarni > > > > -- Yesterday is History. Tomorrow is a Mystery. Today is a Gift! That is why it is called the Present :). http://sites.google.com/site/ramaswamyr --~--~---------~--~----~------------~-------~--~----~ 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 -~----------~----~----~----~------~----~------~--~---
