I could not get your logic of O(n). On Thu, Dec 30, 2010 at 8:07 PM, bhupendra dubey <[email protected]>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 <[email protected]> wrote: > >> You can use binary search >> >> On 12/31/10, Anand <[email protected]> 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 [email protected]. >> > To unsubscribe from this group, send email to >> > [email protected]<algogeeks%[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]<algogeeks%[email protected]> >> . >> 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 [email protected]. > To unsubscribe from this group, send email to > [email protected]<algogeeks%[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.
