Longest Increasing Subsequence

Problem: Longest increasing sequence is the subsequence within a sequence that the elements in the subsequence is in an increasing order. We are trying to find the longest subsequence that has this property. For example, one of the longest increasing subsequences in "17385" is "138".

Solution: This is a classical DP problem. Naive DP solution will give you a O(n^2) algorithm by keep the longest increasing sequence ended at i. A better solution is to use DP alongside with binary search, which will give you a O(nlogn) algorithm. The solution is as follow:

1. having an array M, M[j] stores the ending position of the increasing sequence with length j in the original sequence X. Thus, X[M[j]] should be an increasing sequence as well.
2. iterate the original sequence X, when visiting X[i], do binary search in X[M[j]] to look for the closest position to X[i]. If X[i] is bigger than all the existing X[M[j]], it means if we append X[i] to the end of the current longest increasing sequence, we get a new longest increasing sequence which is longer by 1. Then we update M[L+1] = i (L is the length of current longest increasing sequence).
3. when searching in  in X[M[j]] for X[i], we can also encounter the situation that  X[M[j]]<X[i]< X[M[j+1]]. Then we need to update M[j+1] = i. The reason is that after we have scanned the ith element in X, we need to assure for M[j], we store the increasing sequence of length  j that has the smallest ending element. This will maximize our chance to be able to append further elements to existing increasing sequence.