A fast algorithm for computing a longest common increasing subsequence
Let A =   and B =   be two sequences, where each pair of elements in the sequences is comparable. A common increasing subsequence of A and B is a subsequence  , where i(1) < i(2) < ... < i(1) and j(1) < j(2) < ... < j(l), such that for all 1 less than or equal to k < l, we have a(ik) < a(ik+1). A longest common increasing subsequence of A and B is a common increasing subsequence of the maximum length. This paper presents an algorithm for delivering a longest common increasing subsequence in O(mn) time and O(mn) space. (C) 2004 Elsevier B.V. All rights reserved.
algorithms computational biology longest common subsequence longest increasing subsequence