The Longest Almost Increasing Subsequence Problem with Sliding Windows

In this paper, we first define the longest almost increasing subsequence with sliding windows (LaISW), which is a generalized combination of the longest increasing subsequence with sliding windows (LISW) problem and the longest almost increasing subsequence (LaIS) problem. Given a numeric sequence
$A$
, along with a tolerance constant
$c$
and a window size
$w$
, the LaISW problem aims to find the longest almost increasing subsequence (LaIS) within all windows of size
$w$
, where an almost increasing subsequence allows for slight decreases less than
$c$
. Then, we propose an efficient algorithm to solve the LaISW problem. In our algorithm, we calculate the change of drop out (occurrence) of each element in the row tower, rather than building the entire row tower. The time and space complexities of our algorithm are
$\mathbf{O}(nL)$
and
$\mathbf{O}(L)$
, respectively, where
$n$
denotes the length of the input sequence, and
$L$
denotes the length of the LaISW answer.