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

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

Пусть $𝐱=\{x_1,x_2,\dots ,x_n\}$ — последовательность различных действительных чисел, тогда подпоследовательность $\{x_{i_1},x_{i_2},\dots ,x_{i_k}\}$ чередующаяся, если

$x_{i_1}>x_{i_2}<x_{i_3}>\dots x_{i_k}\wedge 1\le i_1<i_2<\dots <i_k\le n.$

Аналогично, $𝐱$ обратная чередующаяся, если

$x_{i_1}<x_{i_2}>x_{i_3}<\dots x_{i_k}\wedge 1\le i_1<i_2<\dots <i_k\le n.$

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

• ${\mathrm{a}\mathrm{s}}_5(1,2,3,4,5)=2$;
• ${\mathrm{a}\mathrm{s}}_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,$ потому что 5,3,4,1,2 чередующаяся.

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

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

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

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

Если $𝐱$ — случайная перестановка чисел $1,2,\dots ,n$ и $A_n\equiv {\mathrm{a}\mathrm{s}}_n(𝐱)$, тогда можно показать, что

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

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

См. также

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