摘要
Given a positive constant c, a sequence S=〈s <sub>1</sub> ,s <sub>2</sub> ,…,s <sub>k</sub> 〉 of k numbers is said to be almost increasing if and only if s <sub>i</sub> >max1≤j<is <sub>j</sub> −c for all 1<i≤k. A longest common almost-increasing subsequence (LCaIS) between two input sequences is a longest common subsequence that is also an almost increasing sequence. We found out that the existing algorithm proposed by Moosa et al. [1] to find an LCaIS of two sequences without repeated elements gives an incorrect result for some instances. In this work, we present a dynamic programming algorithm that can correctly compute an LCaIS between any two sequences with repeated elements in O(nml) time and O(nm) space, where n and m are the lengths of two input sequences and l is the length of the output LCaIS.