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 ${\displaystyle \mathbf {x} =\{x_{1},x_{2},\ldots ,x_{n}\}}$ is a sequence of distinct real numbers, then the subsequence ${\displaystyle \{x_{i_{1}},x_{i_{2}},\ldots ,x_{i_{k}}\}}$ is alternating[1] (or zigzag or down-up) if

${\displaystyle x_{i_{1}}>x_{i_{2}}<x_{i_{3}}>\cdots x_{i_{k}}\qquad {\text{and}}\qquad 1\leq i_{1}<i_{2}<\cdots <i_{k}\leq n.}$

Similarly, ${\displaystyle \mathbf {x} }$ is reverse alternating (or up-down) if

${\displaystyle x_{i_{1}}<x_{i_{2}}>x_{i_{3}}<\cdots x_{i_{k}}\qquad {\text{and}}\qquad 1\leq i_{1}<i_{2}<\cdots <i_{k}\leq n.}$

Let ${\displaystyle {\rm {as}}_{n}(\mathbf {x} )}$ denote the length (number of terms) of the longest alternating subsequence of ${\displaystyle \mathbf {x} }$. For example, if we consider some of the permutations of the integers 1,2,3,4,5, we have that

• ${\displaystyle {\rm {as}}_{5}(1,2,3,4,5)=2}$; because any sequence of 2 distinct digits are (by definition) alternating. (for example 1,2 or 1,4 or 3,5);
• ${\displaystyle {\rm {as}}_{5}(1,5,3,2,4)=4,}$ because 1,5,3,4 and 1,5,2,4 and 1,3,2,4 are all alternating, and there is no alternating subsequence with more elements;
• ${\displaystyle {\rm {as}}_{5}(5,3,4,1,2)=5,}$ because 5,3,4,1,2 is itself alternating.