The longest common increasing subsequence problem

By reviewing various existing Longest Increasing Subsequence (LIS) and Longest Common Subsequence (LCS) methods, the Longest Common Increasing Subsequence (LCIS) problem is explored in a progressive way. A version of finding LCIS that uses quadratic time and space O(mn) is designed by taking the idea of ordinary dynamic programming with traceback. An optimal space efficient version, which runs in linear space O(m + n), where m and n are the lengths of two sequences, is designed by using the recursive method and compared with the previous quadratic time and space version. A newer version (linear space with mlogm cost for combining subsolutions) that uses both recursive and augmented tree structure technique to reduce the cost for combining subsolutions from O(m(2)) to O(m log m) time in solving the LCIS problem is also designed and implemented.