Longest increasing subsequence problem: Difference between revisions

Revision as of 17:28, 30 March 2006

Revision as of 00:04, 6 April 2006

Line 7:

== Techniques ==

=== Longest Commoncommon Subsequencesubsequence ===

A simple way of finding the longest increasing subsequence is to use the [[longest-common subsequence problem]] ([[dynamic programming]]) algorithm.

Line 13:

#Use [[longest-common subsequence problem]] on with <math>A</math> and <math>B</math>. <math>O(n^2)</math> time.

=== Dynamic Programmingprogramming ===

There is a straight-forward [[dynamic programming]] solution in <math>O(n^2)</math> time. Though this is asymptotically equivalent to the [[longest-common subsequence problem|longest-common subsequence]] version of the solution, the constant is lower, as there is less overhead.

Line 41:

Furthermore, there is at most one difference between the set <math>A_i</math> and the set <math>A_{i+1}</math>, which is caused by this search.

Since <math>A</math> is always ordered in increasing order, and the operation does not change this ordering, we can do a binary search for every single <math>a_1, a_2, \ldots, a_n</math>.

== External links ==