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-which-forms.html >> >> & 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.
