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-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. > -- 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.
