Gawrychowski, Pawel ;
Manea, Florin ;
Serafin, Radoslaw
Fast and Longest Rollercoasters
Abstract
For k >= 3, a krollercoaster is a sequence of numbers whose every maximal contiguous subsequence, that is increasing or decreasing, has length at least k; 3rollercoasters are called simply rollercoasters. Given a sequence of distinct real numbers, we are interested in computing its maximumlength (not necessarily contiguous) subsequence that is a krollercoaster. Biedl et al. (2018) have shown that each sequence of n distinct real numbers contains a rollercoaster of length at least ceil[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 >=slant (k1)^2+1 distinct real numbers contains a krollercoaster of length at least n/(2(k1))  3k/2, and gave an O(nk log n)time (respectively, O(n k log log n)time) algorithm computing a longest krollercoaster in a sequence of length n (respectively, a permutation of {1,...,n}).
In this paper, we give an O(nk^2)time algorithm computing the length of a longest krollercoaster contained in a sequence of n distinct real numbers; hence, for constant k, our algorithm computes the length of a longest krollercoaster in optimal linear time. The algorithm can be easily adapted to output the respective krollercoaster. 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 krollercoaster 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 comparisonbased algorithm computing the length of a longest krollercoaster.
BibTeX  Entry
@InProceedings{gawrychowski_et_al:LIPIcs:2019:10269,
author = {Pawel Gawrychowski and Florin Manea and Radoslaw Serafin},
title = {{Fast and Longest Rollercoasters}},
booktitle = {36th International Symposium on Theoretical Aspects of Computer Science (STACS 2019)},
pages = {30:130:17},
series = {Leibniz International Proceedings in Informatics (LIPIcs)},
ISBN = {9783959771009},
ISSN = {18688969},
year = {2019},
volume = {126},
editor = {Rolf Niedermeier and Christophe Paul},
publisher = {Schloss DagstuhlLeibnizZentrum fuer Informatik},
address = {Dagstuhl, Germany},
URL = {http://drops.dagstuhl.de/opus/volltexte/2019/10269},
doi = {10.4230/LIPIcs.STACS.2019.30},
annote = {Keywords: sequences, alternating runs, patterns in permutations}
}
12.03.2019
Keywords: 

sequences, alternating runs, patterns in permutations 
Seminar: 

36th International Symposium on Theoretical Aspects of Computer Science (STACS 2019)

Issue date: 

2019 
Date of publication: 

12.03.2019 