Introduction
In computer science, the longest increasing subsequence problem is to find a subsequence of a given sequence in which the subsequence’s elements are in sorted order, lowest to highest, and in which the subsequence is as long as possible.
For example, a longest increasing subsequence of 0, 8, 4, 12, 2, 10, 6, 14, 1, 9, 5, 13, 3, 11, 7, 15
is 0, 2, 6, 9, 11, 15
.
An O(N^{2}) Solution
We define a $dp$ table, which $dp[i]$ is the length of a longest subsequence which ends at $inputs[i]$.
For each $inputs[i]$, we search every inputs before it, and choose the longest possible $dp$ value from them, fill it in $dp[i]$.
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 

An O(N*Log(N)) Solution
We define a $seq$ table, which $seq[i]$ is the ending number of subsequence whose length is $i$.
Note that, $seq$ is always in increasing order.
Because if these exist $i < j$ and $seq[i] > seq[j]$, which means a longer subsequence end with a smaller number.
Then we could generate a new subsequence, which length is $i$, by removing $j  i$ numbers from tail of $j$length subsequence. The ending number of the new subsequence will be smaller than $seq[i]$.
Therefore, we can use binary search in each iteration, to find the largest $seq[k]$ which is smaller than $inputs[i]$. If $k$ can be found ($k > 1$), then we update the number stored in $seq[k]$ with $inputs[i]$ if $inputs[i] < seq[k]$.
This yields an O(N*Log(N)) solution.
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 32 33 34 35 36 
