@Prakash: I think we can simplify this to max(product of two smallest numbers and largest number, product of three largest numbers).
Dave On Aug 8, 6:40 am, Prakash D <[email protected]> wrote: > simple soln = max( product of lowest two negative numbers and highest > positive number, product of highest three negative numbers, product of > highest three positive numbers) > > On Mon, Aug 8, 2011 at 4:50 PM, Aditya Virmani > <[email protected]>wrote: > > > > > what if we can maintain three arrays: > > large_positives[3]: containing three largest positive numbers., > > large_negatives[2]: negative numbers with largest magnitude, > > small_negatives[3]: negative numbers with least magnitudes. > > Now thr may be following cases: > > 1) No. of postive numbers >3 & no. of negative numbers>=2, thn max product > > cud be, product of numbers in large_positives or product of largest positive > > number with numbers in large_negatives. > > 2) No. of positive numbers is 0(i.e all negatives), max product wud be > > product of numbers in small_negatives. > > 3)No. of positives is 1(though not required explicitly), product of numbers > > in large_negatives with positive number. > > 4) No. of positives is 2: max product wud be max of, product of two > > positive numbers with small_negative or product of small_negatives. > > Time complexity: O(n) > > Space complexity: O(1) > > I hope all the cases are covered, if not, please correct me > > > On Mon, Aug 8, 2011 at 4:40 PM, Aditya Virmani > > <[email protected]>wrote: > > >> what if the input is all negative? > > >> On Mon, Aug 8, 2011 at 12:57 PM, WgpShashank > >> <[email protected]>wrote: > > >>> hey guys I think we can do it in O(N) Check out > > >>>http://shashank7s.blogspot.com/2011/07/find-three-numbers-in-array-wh... > > >>> & let me know missed something ? > > >>> Thanks > >>> Shashank > >>> CSE,BIT Mesra > > >>> -- > >>> You received this message because you are subscribed to the Google Groups > >>> "Algorithm Geeks" group. > >>> To view this discussion on the web visit > >>>https://groups.google.com/d/msg/algogeeks/-/sC6zcqbh3ZUJ. > > >>> 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?hl=en. > > > -- > > 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?hl=en. -- 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?hl=en.
