Longest Increasing Subsequences in Sliding Windows
[.ps]
[.pdf]
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.
Bibtex Entry
