Overview
The longest increasing subsequence is another good algorithm problem. It is used in physics, mathematics and algorithms. One concrete application is the Patience Diff to find the difference between two files. You can read the wiki.
Content
The Longest Increasing Subsequence of a string finds longest ordered sequence of characters that is in increasing order, but are not necessarily contiguous. In the string “testing”, the LIS is E->I->N.
There are several ways to compute the longest increasing subsequence. The solution with the best time complexity is O(nlogn). The solution I’m going to show runs in O(n^2) but is fairly simple to implement.
You use the Longest Common Subsequence. You send in your word along with the sorted version of your word to the LCS method. Let’s see an example using the word “testing” and the sorted version “eginstt”.
The LCS will build the table shown above. We build a solution the same way we did in the LCS post.
This returns the LIS “ein”.