# Longest Increasing Subsequence

## 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(N2) 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]$.

## 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.