Longest increasing subsequences in windows based on canonical antichain partition
Given a sequence pi(1)pi(2) center dot center dot center dot pi(n), a longest increasing subsequence (LIS) in a window pi   = pi(l)pi(l)+1 center dot center dot center dot pi r is a longest subsequence sigma = pi i(1)pi i(2) center dot center dot center dot pi(iT) such that l   vertical bar 0  , pi   vertical bar i < w}. By maintaining a canonical antichain partition in windows, wer present an optimal output-sensitive algorithm to solve this problem in O (OUTPUT) time, where OUTPUT is the sum of the lengths of the n + w - 1 LISs in those windows of S-FIX. In addition, we propose a more generalized problem called LISSET problem, which is to find a LIS for every window in a set S-VAR containing variable-size windows. By applying our algorithm, we provide an efficient solution for the LISSET problem to output a LIS (or all the LISs) in every window which is better than the straightforward generalization of classical LIS algorithms. An upper bound of our algorithm on the LISSET problem is discussed. (c) 2007 Elsevier B. V. All rights reserved.
longest increasing subsequences canonical antichain partition data streaming model