@pawan Will it not take O(n^2) time then. What he is talking about is solving it in O(nlogn) time
Anurag Sharma http://anuragsharma-sun.blogspot.com/ On Sat, May 29, 2010 at 7:04 PM, pawan sharma <pawanprakash...@gmail.com>wrote: > @amit > for longest increasing subsequence , just sort the given array and find > longest subsequence of sorted array and unsorted array . It will give you > longest increasing subsequence (because of sorted array) . > > > On Sat, May 29, 2010 at 12:41 PM, Nikhil Agarwal < > nikhil.bhoja...@gmail.com> wrote: > >> Check: >> >> http://www.algorithmist.com/index.php/Longest_Increasing_Subsequence >> >> >> >> >> >> On Sat, May 29, 2010 at 4:15 AM, Amir hossein Shahriari < >> amir.hossein.shahri...@gmail.com> wrote: >> >>> A hint from "Introduction to algorithms" on this problem: >>> Observe that the last element of a candidate subsequence of length *i* is >>> at least as large as the last element of a candidate subsequence of length >>> *i-1. *Maintain candidate subsequences by linking them through the input >>> sequence >>> >>> The attached file is a tutorial from train.usaco.org which includes 3 >>> approaches to the problem and explains them with some examples. >>> I hope it would help! >>> >>> >>> On Fri, May 28, 2010 at 7:44 PM, amit <amitjaspal...@gmail.com> wrote: >>> >>>> Hi , Can anyone plz explain this algorithm taking some example. >>>> I read this on wiki but could'nt get how binary search was working. >>>> >>>> -- >>>> You received this message because you are subscribed to the Google >>>> Groups "Algorithm Geeks" group. >>>> To post to this group, send email to algoge...@googlegroups.com. >>>> To unsubscribe from this group, send email to >>>> algogeeks+unsubscr...@googlegroups.com<algogeeks%2bunsubscr...@googlegroups.com> >>>> . >>>> 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 algoge...@googlegroups.com. >>> To unsubscribe from this group, send email to >>> algogeeks+unsubscr...@googlegroups.com<algogeeks%2bunsubscr...@googlegroups.com> >>> . >>> For more options, visit this group at >>> http://groups.google.com/group/algogeeks?hl=en. >>> >> >> >> >> -- >> Thanks & Regards >> Nikhil Agarwal >> Senior Undergraduate >> Computer Science & Engineering, >> National Institute Of Technology, Durgapur,India >> http://tech-nikk.blogspot.com >> http://beta.freshersworld.com/communities/nitd >> >> >> -- >> You received this message because you are subscribed to the Google Groups >> "Algorithm Geeks" group. >> To post to this group, send email to algoge...@googlegroups.com. >> To unsubscribe from this group, send email to >> algogeeks+unsubscr...@googlegroups.com<algogeeks%2bunsubscr...@googlegroups.com> >> . >> 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 algoge...@googlegroups.com. > To unsubscribe from this group, send email to > algogeeks+unsubscr...@googlegroups.com<algogeeks%2bunsubscr...@googlegroups.com> > . > 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 algoge...@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?hl=en.
