Let A and B be two number sequences of length n and m, respectively, where \(m\le n\) . Given a positive number \(\delta \) , a common almost increasing sequence \(s_1\ldots s_k\) is a common subsequence for both A and B such that for all \(2\le i\le k\) , \(s_i+\delta > \max _{1\le j < i} s_j\) . The LCaIS problem seeks to find the longest common almost increasing subsequence (LCaIS) of A and B. An LCaIS can be computed in \(O(nm\ell )\) time and O(nm) space [Ta, Shieh, Lu (TCS 2021)], where \(\ell \) is the length of the LCaIS of A and B. In this paper we first give an \(O(nm\ell )\) -time and \(O(n+m\ell )\) -space algorithm to find LCaIS, which improves the space complexity. We then design an \(O((n+m)\log n +\mathcal {M}\log \mathcal {M} + \mathcal {C}\ell )\) -time and \(O(\mathcal {M}(\ell +\log \mathcal {M}))\) -space algorithm, which is faster when the number of matching pairs \(\mathcal {M}\) and the number of compatible matching pairs \(\mathcal {C}\) are in \(o(nm/\log m)\) .