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

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

Пусть $\mathbf {x} =\{x_{1},x_{2},\ldots ,x_{n}\}$ — последовательность различных действительных чисел, тогда подпоследовательность $\{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}$ обратная чередующаяся, если

$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.$

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

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

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

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

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

Вероятностные оценки

Если $\mathbf {x}$ — случайная перестановка чисел $1,2,\ldots ,n$ и $A_{n}\equiv {\rm {as}}_{n}(\mathbf {x} )$, тогда можно показать, что

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

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

См. также

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