## 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.