Longest increasing subsequence problem: Difference between revisions

Revision as of 05:59, 25 August 2006

Revision as of 06:53, 25 August 2006

Line 16:

=== Dynamic programming ===

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.

Given the sequence <math>a_0,a_1,a_2,\ldots,a_k</math>, the optimal way to add <math>a_{k+1}</math> would simply be the longest of the longest subsequence from <math>a_i</math> to <math>a_k+1</math>, adding it to each list if needed. For each <math>a_k+1</math>, there are two possibilities: