http://codepad.org/EWcoJ2c3
Here is solution for find the Longest Increasing subseqence. I tried two approach. 1. Find the suboptimal solution using O(n) complexity thereby optimal solution for the problem reaches O(n^2). 2. Find the suboptimal solution using O(logn) complexity thereby optimal solution for the problem reaches O(nlogn). On Fri, Jun 4, 2010 at 11:49 PM, Anand <anandut2...@gmail.com> wrote: > > http://codepad.org/NDAeIpxR > > Here is code for it > On Sat, May 29, 2010 at 7:45 PM, Anurag Sharma <anuragvic...@gmail.com>wrote: > >> @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<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.
