I could not get your logic of O(n). On Thu, Dec 30, 2010 at 8:07 PM, bhupendra dubey <bhupendra....@gmail.com>wrote:
> It can be done in O(n) time. > > int start_index=0, longest_sequence=0 > > traverse the sequence and increment 't' for every a[i+1]>a[i] > starting with zero till this holds true. > > assign 't' to longest_sequence > > assuming condition evaluates to false for a[k]; > repeat the above step but assign 't' to longest_sequence only when > t>longest_sequence > also change start_index to 'k' > > do this for the whole array. > > > > On Fri, Dec 31, 2010 at 8:20 AM, Prabakaran N <prabaf...@gmail.com> wrote: > >> You can use binary search >> >> On 12/31/10, Anand <anandut2...@gmail.com> wrote: >> > Anyone know how to find longest increasing subsequence in O(nlogn) >> > complexity? >> > >> > -- >> > 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. >> >> > > > -- > bhupendra dubey > > -- > 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.
