article · Theoretical Computer Science · 2025
The merged longest common increasing subsequence problem
C. A. Lee, Chang‐Biau Yang, Kuo-Si Huang
Cited by 0Open access
Abstract
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.
Cite this paper
Lee, C. A., Yang, C., & Huang, K.-S. (2025). The merged longest common increasing subsequence problem. Theoretical Computer Science, 1044, 115269. https://doi.org/10.1016/j.tcs.2025.115269
Lee, C. A., et al. “The merged longest common increasing subsequence problem.” Theoretical Computer Science, vol. 1044, 2025, p. 115269, https://doi.org/10.1016/j.tcs.2025.115269.
Lee, C. A., Chang‐Biau Yang, and Kuo-Si Huang. 2025. “The merged longest common increasing subsequence problem.” Theoretical Computer Science 1044: 115269. https://doi.org/10.1016/j.tcs.2025.115269.
Lee, C.A., Yang, C. and Huang, K.-S. (2025) ‘The merged longest common increasing subsequence problem’, Theoretical Computer Science, 1044, p. 115269. Available at: https://doi.org/10.1016/j.tcs.2025.115269.
@article{lee2025merged,
title = {{The merged longest common increasing subsequence problem}},
author = {Lee, C. A. and Yang, Chang‐Biau and Huang, Kuo-Si},
journal = {Theoretical Computer Science},
volume = {1044},
pages = {115269},
year = {2025},
doi = {10.1016/j.tcs.2025.115269}
}Made from the index record. Check names, capitalisation and page numbers against the paper. Need another style? AI for Research has over 10,000.