A Space Efficient Algorithm for LCIS Problem

This paper reformulates the problem of finding a longest common increasing subsequence of the two given input sequences in a very succinct way. An extremely simple linear space algorithm based on the new formula can find a longest common increasing subsequence of sizes n and m respectively, in time O(nm) using additional \(\min \{n,m\}\,+\,1\) space.