  For $k\geq 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 $\lceil n/2\rceil$ for $n>7$, and
that a longest rollercoaster contained in such a sequence can be computed in
$O(n\log n)$-time. They have also shown that every sequence of $n\geq
(k-1)^2+1$ distinct real numbers contains a $k$-rollercoaster of length at
least $\frac{n}{2(k-1)}-\frac{3k}{2}$, and gave an $O(nk\log 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 \log^2 n)$-time, that is,
subquadratic even for large values of $k\leq 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.
