Longest increasing subsequences in sliding windows (Q1885912): Difference between revisions

Given a sequence \(a_1a_2\dots a_n\) of distinct values from a linearly ordered set, its Longest Increasing Subsequence (LIS) is a subsequence of maximum length, whose values increase as the indices increase. The longest increasing subsequence problem refers either to identifying the longest increasing subsequence(s) or, alternatively, to determining the length of the LIS. In this paper the authors consider the problem (LISW) of listing a longest increasing subsequence in every window of given width \(w\). An obvious naïve algorithm for LISW is to simply compute their LIS in each window independently. Using, for example, an \(O(n\log\log n)\) LIS algorithm of \textit{S. Bespamyatnikh} and \textit{M. Segal} [``Enumerating longest increasing subsequences and patience sorting'', Inform. Process. Lett. 76, 7--11 (2000)] that determines all LISs in a sequence of length \(n\), this gives an \(O(nw \log \log n)\) algorithm. However, by using a data structure which gives the LISs of all suffixes of the current window and which can easily be updated each time we slide the window across, dropping an element off the beginning and adding one to the end, the authors obtain an \(O(n\log \log n + OUTPUT)\) algorithm, where \(OUTPUT\) is the size of the output from the algorithm. In the case where the average length of the LIS in each window is \(\Theta(w)\), the authors' algorithm offers no improvement over the naïve method. However, given that the expected length of each LIS in a random sequence is \(O(\sqrt{w})\), then the authors' algorithm is \(O(n\sqrt{w})\) whereas the naïve algorithm is \(O(nw\log \log n)\). The algorithm uses a generalization of the Robinson-Schensted-Knuth algorithm [see \textit{M. van Leeuwen}, ``The Robinson-Schensted and Schützenberger algorithms, an elementary approach'', Electron. J. Comb. 3, No. 2, Research paper R15, 32 p. (1996); printed version J. Comb. 3, No. 2, 391--422 (1996; Zbl 0852.05080), and also \textit{D. E. Knuth}, The art of computer programming. Vol. 3. Sorting and searching. Addison-Wesley, Reading, Mass. (1974; Zbl 0302.68010)]. Other variations of the problem remain open, in particular the exact time complexity of the problem of finding the window with the longest increasing sequence among all windows.