Largest alternating subsequence

In combinatorics, probability theory, and computer science, the problem of the greatest alternating subsequence is to find a subsequence of the greatest length of a given sequence such that its elements are arranged in an alternating manner.

Let be $\mathbf {x} =\{x_{1},x_{2},\ldots ,x_{n}\}$ ${\ displaystyle \ mathbf {x} = \ {x_ {1}, x_ {2}, \ ldots, x_ {n} \}}$ ${\ displaystyle \ mathbf {x} = \ {x_ {1}, x_ {2}, \ ldots, x_ {n} \}}$ Is a sequence of different real numbers, then a subsequence $\{x_{i_{1}},x_{i_{2}},\ldots ,x_{i_{k}}\}$ ${\ displaystyle \ {x_ {i_ {1}}, x_ {i_ {2}}, \ ldots, x_ {i_ {k}} \}}$ ${\ displaystyle \ {x_ {i_ {1}}, x_ {i_ {2}}, \ ldots, x_ {i_ {k}} \}}$ alternating if

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.

{\ 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.}

{\ 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 $\mathbf {x}$ ${\ displaystyle \ mathbf {x}}$ $\ mathbf {x}$ reverse alternating if

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.

{\ 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.}

{\ 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 be ${\rm {as}}_{n}(\mathbf {x} )$ ${\ displaystyle {\ rm {as}} _ {n} (\ mathbf {x})}$ ${\ displaystyle {\ rm {as}} _ {n} (\ mathbf {x})}$ denotes the length (number of elements) of the largest alternating subsequence of the sequence $\mathbf {x}$ ${\ displaystyle \ mathbf {x}}$ $\ mathbf {x}$ . For example, if we consider some permutation of the numbers 1,2,3,4,5, we get

${\rm {as}}_{5}(1,2,3,4,5)=2$ ${\ displaystyle {\ rm {as}} _ {5} (1,2,3,4,5) = 2}$ ${\ displaystyle {\ rm {as}} _ {5} (1,2,3,4,5) = 2}$ ;
${\rm {as}}_{5}(1,5,3,2,4)=4,$ ${\ displaystyle {\ rm {as}} _ {5} (1,5,3,2,4) = 4,}$ ${\ 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 alternating, and there is no alternating subsequence of more elements;
${\rm {as}}_{5}(5,3,4,1,2)=5,$ ${\ displaystyle {\ rm {as}} _ {5} (5,3,4,1,2) = 5,}$ ${\ displaystyle {\ rm {as}} _ {5} (5,3,4,1,2) = 5,}$ because 5,3,4,1,2 alternating.

Effective Algorithm

The problem of the greatest alternating subsequence is solved in time $O(n)$ ${\ displaystyle O (n)}$ $O(n)$ where $n$ ${\ displaystyle n}$ $n$ Is the length of the original sequence.

Probabilistic estimates

If a $\mathbf {x}$ ${\ displaystyle \ mathbf {x}}$ $\mathbf {x}$ - random permutation of numbers $1,2,\ldots ,n$ ${\ displaystyle 1,2, \ ldots, n}$ $1,2,\ldots ,n$ and $A_{n}\equiv {\rm {as}}_{n}(\mathbf {x} )$ ${\ displaystyle A_ {n} \ equiv {\ rm {as}} _ {n} (\ mathbf {x})}$ $A_{n}\equiv {\rm {as}}_{n}(\mathbf {x} )$ , then it can be shown that

E[A_{n}]={\frac {2n}{3}}+{\frac {1}{6}}\qquad {\text{and}}\qquad \operatorname {Var} [A_{n}]={\frac {8n}{45}}-{\frac {13}{180}}.

{\ displaystyle E [A_ {n}] = {\ frac {2n} {3}} + {\ frac {1} {6}} \ qquad {\ text {and}} \ qquad \ operatorname {Var} [A_ {n}] = {\ frac {8n} {45}} - {\ frac {13} {180}}.}

E[A_{n}]={\frac {2n}{3}}+{\frac {1}{6}}\qquad {\text{and}}\qquad \operatorname {Var} [A_{n}]={\frac {8n}{45}}-{\frac {13}{180}}.

Moreover, with $n\rightarrow \infty$ ${\ displaystyle n \ rightarrow \ infty}$ $n \rightarrow \infty$ random value $A_{n}$ ${\ displaystyle A_ {n}}$ $A_{n}$ centered, normalized, its distribution tends to normal.

Largest alternating subsequence

Effective Algorithm

Probabilistic estimates

See also

More articles: