Fast and Longest Rollercoasters
share
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 numbers, we are interested in computing its maximum-length (not necessarily contiguous) subsequence that is a k-rollercoaster. Biedl et al. [ICALP 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 n)-time. 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 n)-time algorithm computing a longest k-rollercoaster in a sequence of length n. In this paper, we give an O(nk^2)-time algorithm computing 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. [ICALP 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 ^2 n)-time, that is, subquadratic even for large values of k≤ n. Again, the rollercoaster can be easily retrieved. Finally, we show an Ω(n k) lower bound for the number of comparisons in any comparison-based algorithm computing the length of a longest k-rollercoaster.
READ FULL TEXT