Explorations on the longest common increasing subsequence problem.

摘要

By reviewing various existing Longest Increasing Subsequence (LIS) and Longest Common Subsequence (LCS) methods, Longest Common Increasing Subsequence (LCIS) problem is explored in a progressive way. Three basic cases of LCIS are analyzed in detail by significant extensions to Gries' LIS method. A version of finding LCIS, which takes quadratic time and space, is designed by taking the idea of ordinary dynamic programming with traceback. A space efficient version, which runs in linear space, is implemented through using 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(m2) to O(mlogm) time in solving LCIS problem is designed and implemented.