Fast and Longest Rollercoasters
Paweł Gawrychowski, Florín Manea, Radosław Serafin · Algorithmica · 2022
Abstract For $$k\ge 3$$ k≥3 , ak-rollercoasteris a sequence of numbers whose every maximal contiguous subsequence, that is increasing or decreasing, has length at leastk; 3-rollercoasters are called simply rollercoasters. Given a sequence of distinct real numbers, we are interested in computing its maximum-length (not necessarily contiguous) subsequence that is ak-rollercoaster. Biedl et al. (in: ICALP, volume 107 of LIPIcs. Schloss Dagstuhl - Leibniz-Zentrum fuer Informatik, pp 18:1–18:15, 2018) have shown that each sequence ofndistinct real numbers contains a rollercoaster of length at least $$\lceil n/2\rceil $$ ⌈n/2⌉ for $$n>7$$ n>7 , and that a longest rollercoaster contained in such a sequence can be computed in $$O(n\log n)$$ O(nlogn) -time (or faster, in $$O(n \log \log n)$$ O(nloglogn) time, when the input sequence is a permutation of $$\{1,\ldots ,n\}$$ {1,…,n} ). They have also shown that every sequence of $$n\geqslant (k-1)^2+1$$ n⩾(k-1)2+1 distinct real numbers contains ak-rollercoaster of length at least $$\frac{n}{2(k-1)}-\frac{3k}{2}$$ n2(k-1)-3k2 , and gave an $$O(nk\log n)$$ O(nklogn) -time (respectively, $$O(n k\log \log n)$$ O(nkloglogn) -time) algorithm computing a longestk-rollercoaster in a sequence of lengthn(respectively, a permutation of $$\{1,\ldots ,n\}$$ {1,…,n} ). In this paper, we give an $$O(nk^2)$$ O(nk2) -time algorithm computing the length of a longestk-rollercoaster contained in a sequence ofndistinct real numbers; hence, for constantk, our algorithm computes the length of a longestk-rollercoaster in optimal linear time. The algorithm can be easily adapted to output the respectivek-rollercoaster. In particular, this improves the results of Biedl et al. (2018), by showing that a longest rollercoaster can be computed in optimal linear time. We also present an algorithm computing the length of a longestk-rollercoaster in $$O(n \log ^2 n)$$ O(nlog2n) -time, that is, subquadratic even for large values of $$k\le n$$ k≤n . Again, the rollercoaster can be easily retrieved. Finally, we show an $$\Omega (n \log k)$$ Ω(nlogk) lower bound for the number of comparisons in any comparison-based algorithm computing the length of a longestk-rollercoaster.