Longest Increasing Subsequences in Sliding Windows

[.ps] [.pdf]


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.

Bibtex Entry