===#REDIRECT [[Longest commonincreasing subsequence ===]]▼The '''longest increasing subsequence''' problem is to find the longest increasing [[subsequence]] of a given sequence. It also reduces to a [[graph theory]] problem of finding the longest path in a [[directed acyclic graph]].
Note that subsequence we are searching for is not necessarily contiguous. Searching for the longest ''contiguous'' sequence would be the [[longest common substring problem]], an easier problem to solve.
== Overview ==
Formally, the problem is as follows:
Given a sequence <math>a_0,a_1,a_2,\ldots,a_n</math>, find the longest subset such that for every <math>i < j</math>, <math>a_i < a_j</math>.
== Techniques ==
▲=== Longest common subsequence ===
A simple way of finding the longest increasing subsequence is to use the [[longest common subsequence problem]] ([[dynamic programming]]) algorithm.
#Make a [[sorting|sorted]] copy of the sequence <math>A</math>, denoted as <math>B</math>. <math>O(n \lg(n) )</math> time.
#Use [[longest-common subsequence problem]] on with <math>A</math> and <math>B</math>. <math>O(n^2)</math> time.
=== 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:
*The number is lower than the last number of the subsequence and greater than the second last. In this case the last number of the subsequence is replaced by the new number.
*The number is greater than the last number of the subsequence: The number is appended to the subsequence and if this subsequence is the best subsequence with this length, it will be stored.
The pseudo-code is show below:
<pre>
func lis( a )
initialize best to an array of 0's.
for ( i from 1 to n )
best[i] = 1
for ( j from 1 to i - 1 )
if ( a[i] > a[j] )
best[i] = max( best[i], best[j] + 1 )
return max( best )
</pre>
There's also an <math>O(n \lg{n})</math> solution based on some observations. Let <math>A_{i,j}</math> be the smallest possible tail out of all increasing subsequences of length <math>j</math> using elements <math>a_1, a_2, a_3, \ldots, a_i</math>.
Observe that, for any particular <math>i</math>, <math>A_{i,1} < A_{i,2} < \ldots < A_{i,j}</math>. This suggests that if we want the longest subsequence that ends with <math>a_{i+1}</math>, we only need to look for a <math>j</math> such that <math>A_{i,j} < a_{i+1} <= A_{i,j+1}</math> and the length will be <math>j+1</math>.
Notice that in this case, <math>A_{i+1,j+1}</math> will be equal to <math>a_{i+1}</math>, and all <math>A_{i+1, k}</math> will be equal to <math>A_{i,k}</math> for <math>k \ne j + 1</math>.
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 ==
*[http://www.algorithmist.com/index.php/Longest_Increasing_Subsequence Algorithmist's Longest Increasing Subsequence] - Where this article was taken.
*[http://www2.toki.or.id/book/AlgDesignManual/BOOK/BOOK2/NODE47.HTM#SECTION02314000000000000000 Another explanation of the problem]
[[Category:Algorithms on strings]]
[[Category:Combinatorics]]
[[Category:Formal languages]]
[[Category:Dynamic programming]]
[[Category:Graph theory]]
| 