The Merged Longest Common Increasing Subsequence Problem

In this paper, we first define the merged longest common increasing subsequence (MLCIS) problem, a composite variant combining the longest common subsequence (LCS) problem and longest increasing subsequence (LIS) problem. Given a pair of sequences A and B, along with a target sequence T, the goal of the MLCIS problem is to find the subsequence with the maximal length that is both common and increasing in both E(A, B) and T. Here, E(A, B) denotes any new sequence obtained by arbitrarily merging A and B while preserving their original orders. We propose a dynamic programming algorithm for solving the MLCIS problem. The time complexity of our algorithm is O(mnr), where m, n and r represent the lengths of sequences A, B and T, respectively.