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

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

Пусть ${\displaystyle \mathbf {x} =\{x_{1},x_{2},\ldots ,x_{n}\}}$ — последовательность различных действительных чисел, тогда подпоследовательность ${\displaystyle \{x_{i_{1}},x_{i_{2}},\ldots ,x_{i_{k}}\}}$ чередующаяся, если

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

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

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

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

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

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

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

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

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

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

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

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

См. также

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