Longest Increasing Subsequences in Sliding Windows. M.H. Albert, A. Golynski, A.M. Hamel, A. Lspez-Ortiz S. S. Rao and M.A. Safari. Theoretical Computer Science, vol. 321, pp. 405-414, 2004. [Postscript file]
Abstract.
We consider the problem of finding the longest increasing subsequence in a sliding window over a given sequence (LISW). We propose an output-sensitive data structure for the LISW problem. We propose a data structure which solves this problem in time O(n log log n + output) for a sequence of n elements. This data structure substantially improves over the naive generalization of the longest increasing subsequence algorithm and is, in fact an output-sensitive optimal solution.