Fast and Longest Rollercoasters

For k >= 3, a k-rollercoaster is a sequence of numbers whose every maximal contiguous subsequence, that is increasing or decreasing, has length at least k; 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 a k-rollercoaster. Biedl et al. (in: ICALP, volume 107 of LIFIcs. Schloss Dagstuhl - Leibniz-Zentrum fuer Informatik, pp 18:1-18:15, 2018) have shown that each sequence of n distinct real numbers contains a rollercoaster of length at least [n/2] for n > 7, and that a longest rollercoaster contained in such a sequence can be computed in O(n log n)-time (or faster, in O (n log log n) time, when the input sequence is a permutation of {1, . . . , n}). They have also shown that every sequence of n >= (k - 1)(2) + 1 distinct real numbers contains a k-rollercoaster of length at least n/2(k-1) - 3k/2, and gave an O(nk log n)-time (respectively, O(nk log log n)-time) algorithm computing a longest k-rollercoaster in a sequence of length n (respectively, a permutation of {1, . . . , n}). In this paper, we give an O(nk(2))-time algorithm com- puting the length of a longest k-rollercoaster contained in a sequence of n distinct real numbers; hence, for constant k, our algorithm computes the length of a longest k-rollercoaster in optimal linear time. The algorithm can be easily adapted to output the respective k-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 longest k-rollercoaster in O (n log(2)n)-time, that is, subquadratic even for large values of k <= n. Again, the rollercoaster can be easily retrieved. Finally, we show an Omega(n log k) lower bound for the number of comparisons in any comparison-based algorithm computing the length of a longest k-rollercoaster.

Automated summary

This paper introduces algorithms for computing the length of a maximum-length k-rollercoaster in a given sequence, improving upon previous results in terms of complexity and output.