Наибольшая чередующаяся подпоследовательность

В комбинаторике, теории вероятности и информатике задача о наибольшей чередующейся подпоследовательности состоит в том, чтобы найти подпоследовательность наибольшей длины заданной последовательности, такую, что её элементы расположены чередующимся образом.

Пусть $\mathbf{x}=\{x_1,x_2,\dots <!--\; \dots \; -->,x_n\}$$\mathbf {x} =\{x_{1},x_{2},\ldots ,x_{n}\}$ — последовательность различных действительных чисел, тогда подпоследовательность $\{x_{i_1},x_{i_2},\dots <!--\; \dots \; -->,x_{i_k}\}$$\{x_{i_{1}},x_{i_{2}},\ldots ,x_{i_{k}}\}$ чередующаяся, если

$x_{i_{1}}>x_{i_{2}}<x_{i_{3}}>\ldots x_{i_{k}}\qquad \land \qquad 1\leq i_{1}<i_{2}<\ldots <i_{k}\leq n.$

Аналогично, $\mathbf{x}$$\mathbf {x}$ обратная чередующаяся, если

$x_{i_{1}}<x_{i_{2}}>x_{i_{3}}<\ldots x_{i_{k}}\qquad \land \qquad 1\leq i_{1}<i_{2}<\ldots <i_{k}\leq n.$

Пусть ${\mathrm{a}\mathrm{s}}_n(\mathbf{x})$${\rm {as}}_{n}(\mathbf {x} )$ обозначает длину(число элементов) наибольшей чередующейся подпоследовательности последовательности $\mathbf{x}$$\mathbf {x}$. Например, если рассмотреть некоторую перестановку чисел 1,2,3,4,5, получится

• ${\mathrm{a}\mathrm{s}}_5(1,2,3,4,5)=2$${\rm {as}}_{5}(1,2,3,4,5)=2$;
• ${\mathrm{a}\mathrm{s}}_5(1,5,3,2,4)=4,$${\rm {as}}_{5}(1,5,3,2,4)=4,$ потому что 1,5,3,4 и 1,5,2,4 и 1,3,2,4 чередующиеся, и нет чередующейся подпоследовательности из большего числа элементов;
• ${\mathrm{a}\mathrm{s}}_5(5,3,4,1,2)=5,$${\rm {as}}_{5}(5,3,4,1,2)=5,$ потому что 5,3,4,1,2 чередующаяся.

Эффективный алгоритмПравить

Задача о наибольшей чередующейся подпоследовательности решается за время $O(n)$$O(n)$ , где $n$$n$  — длина исходной последовательности.

Также за время $O(n)$$O(n)$  можно решить задачу о наибольшей чередующейся подпоследовательности с лексикографически минимальным множеством индексов, хоть это и заметно более сложная задача.

Вероятностные оценкиПравить

Если $\mathbf{x}$$\mathbf {x}$  — случайная перестановка чисел $1,2,\dots <!--\; \dots \; -->,n$$1,2,\ldots ,n$  и $A_n\equiv <!--\; \equiv \; -->{\mathrm{a}\mathrm{s}}_n(\mathbf{x})$$A_{n}\equiv {\rm {as}}_{n}(\mathbf {x} )$ , тогда можно показать, что

$E[A_n]=\frac{2n}{3}+\frac{1}{6}\text{and}\mathrm{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}}.$ 

Более того, при $n\to <!--\; \to \; -->\mathrm{\infty <!--\; \infty \; -->}$$n \rightarrow \infty$  случайная величина $A_n$$A_{n}$  центрированная, нормированная, её распределение стремится к нормальному.

См. такжеПравить

• Наибольшая увеличивающаяся подпоследовательность
• Наибольшая общая подпоследовательность
• Чередующаяся перестановка