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
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
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
This is a very common problem. Search for 'Longest Increasing Subsequence' at
Google.
Muntasir
- Original Message -
From: monty 1987
To: [EMAIL PROTECTED]
Sent: Saturday, April 14, 2007 5:52 PM
Subject: [algogeeks] algo problem
My problem is to find out longest