Linear time isn't enough. Think about what the term 'subsequence' means.
Muntasir
----- Original Message -----
From: Hari Nathan
To: [email protected]
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:* [email protected]
> > *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 [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
-~----------~----~----~----~------~----~------~--~---
