Content deleted Content added
Nkojuharov (talk | contribs) mNo edit summary |
Nkojuharov (talk | contribs) No edit summary |
||
Line 14:
=== 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:
| |||