Longest alternating subsequence

In combinatorial mathematics, probability, and computer science, in the longest alternating subsequence problem, one wants to find a subsequence of a given sequence in which the elements are in alternating order, and in which the sequence is as long as possible.
Formally, if formula_1 is a sequence of distinct real numbers, then the subsequence formula_2 is "alternating" (or "zigzag" or "down-up")if
Similarly, formula_4 is "reverse alternating" (or "up-down") if 
Let formula_6 denote the length (number of terms) of the longest alternating subsequence of formula_4. For example, if we consider some of the permutations of the integers 1,2,3,4,5, we have that
Efficient algorithms.
The longest alternating subsequence problem is solvable in time formula_11, where formula_12 is the length of the original sequence.
Distributional results.
If formula_4 is a random permutation of the integers formula_14 and formula_15, then it is possible to show
that
Moreover, as formula_17, the random variable formula_18, appropriately centered and scaled, converges to a standard normal distribution.
Online algorithms.
The longest alternating subsequence problem has also been studied in the setting of online algorithms, in which the elements of formula_4 are presented in an online fashion, and a decision maker needs to decide whether to include or exclude each element at the time it is first presented, without any knowledge of the elements that will be presented in the future,
and without the possibility of recalling on preceding observations.
Given a sequence formula_20 of independent random variables with common continuous distribution formula_21, it is possible to construct a selection procedure that maximizes the expected number of alternating selections. 
Such expected values can be tightly estimated, and it equals formula_22.
As formula_17, the optimal number of online alternating selections appropriately centered and scaled converges to a normal distribution.