The merged longest common increasing subsequence problem

The merged longest common increasing subsequence (MLCIS) problem represents a generalized variant by combining the merged longest common subsequence (merged LCS, MLCS) problem and the longest increasing subsequence (LIS) problem. Given a pair of numeric sequences A and B along with a target numeric sequence T , the MLCIS problem aims to identify the longest common subsequence that is increasing in both the merged sequence E ( A , B ) and the target sequence T . Here, E ( A , B ) represents a new sequence constructed from arbitrarily merging A and B while maintaining their original orders. In this paper, we propose two algorithms for solving the MLCIS problem: dynamic programming and diagonal. The dynamic programming algorithm has a time complexity of O( mnr ), where m , n and r denote the lengths of sequences A , B and T , respectively. The time complexity of the diagonal algorithm is O( ( L + 1 ) ( r − L + 1 ) ( m + n ) ), where L denotes the length of the MLCIS answer. In general, as the experimental results show, the diagonal algorithm is more efficient than the dynamic programming algorithm in practice. Furthermore, the diagonal algorithm is very efficient when L is either very small or L is close to r , which coincides with the theoretical time complexity. • This paper defines the merged longest common increasing subsequence (MLCIS) problem. • The MLCIS problem is a combined generalization of the merged LCS and the longest increasing subsequence (LIS) problems. • We solve the problem with two approaches: dynamic programming and diagonal methods. • In the diagonal method, the number of elements in a cell is bounded by the maximal cardinality in the upper-left triangle. • The diagonal method is very efficient when the answer length is either very small or close to the target sequence length.