Linear time isn't enough. Think about what the term 'subsequence' means. Muntasir ----- Original Message ----- From: Hari Nathan To: algogeeks@googlegroups.com Sent: Tuesday, April 17, 2007 9:52 AM Subject: [algogeeks] Re: algo problem
Isn't linear time enough? Go form the begining to the end, whenever a[i] > a[i+1] you a new subsequence. You can keep track of where each one ends and then pick the longest. On 4/15/07, Sachin <[EMAIL PROTECTED]> wrote: http://en.wikipedia.org/wiki/Longest_increasing_subsequence_problem This link depicts an algorithm, which is O(nlogn) algo. Approach: dynamic programming. On 4/15/07, Daniel Bastidas <[EMAIL PROTECTED]> wrote: > if you can find the programming challenge book, there is a Longest > Increasing Subsequence algorithm > > On 4/14/07, Muntasir Azam Khan <[EMAIL PROTECTED]> wrote: > > > > This is a very common problem. Search for 'Longest Increasing > > Subsequence' at Google. > > > > Muntasir > > > > ----- Original Message ----- > > > > *From:* monty 1987 <[EMAIL PROTECTED] > > > *To:* algogeeks@googlegroups.com > > *Sent:* Saturday, April 14, 2007 5:52 PM > > *Subject:* [algogeeks] algo problem > > > > My problem is to find out longest subsequence of integers in increasing > > order in an array of integers. > > If any one have solution tell it to me. > > > > > > > > > > > --~--~---------~--~----~------------~-------~--~----~ You received this message because you are subscribed to the Google Groups "Algorithm Geeks" group. To post to this group, send email to algogeeks@googlegroups.com To unsubscribe from this group, send email to [EMAIL PROTECTED] For more options, visit this group at http://groups.google.com/group/algogeeks -~----------~----~----~----~------~----~------~--~---