1 Answers
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 x = { x 1 , x 2 , … , x n } {\displaystyle \mathbf {x} =\{x_{1},x_{2},\ldots ,x_{n}\}} is a sequence of distinct real numbers, then the subsequence { x i 1 , x i 2 , … , x i k } {\displaystyle \{x_{i_{1}},x_{i_{2}},\ldots ,x_{i_{k}}\}} is alternating if
Similarly, x {\displaystyle \mathbf {x} } is reverse alternating if
Let a s n {\displaystyle {\rm {as}}_{n}} denote the length of the longest alternating subsequence of x {\displaystyle \mathbf {x} }. For example, if we consider some of the permutations of the integers 1,2,3,4,5, we have that