Computing a longest common almost-increasing subsequence of two sequences

Given a positive constant c , a sequence S = (s(1) , s(2) , ... , s(k)) of k numbers is said to be almost increasing if and only if s(i) > max(1 <= j <= i) s(j) - 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. (C) 2020 Elsevier B.V. All rights reserved.

Automated summary

In this work, a dynamic programming algorithm is proposed to correctly compute the longest common almost-increasing subsequence (LCaIS) between two sequences with repeated elements. The algorithm has a time complexity of O(nml) and a space complexity of O(nm).