Самая длинная чередующаяся подпоследовательность

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

Формально, если $\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}}>\cdots x_{i_{k}}\qquad {\text{and}}\qquad 1\leq i_{1}<i_{2}<\cdots <i_{k}\leq n.$

Сходным образом, $\mathbf {x}$ является обратным чередованием (или вверх-вниз ), если

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

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

• ${\rm {as}}_{5}(1,2,3,4,5)=2$; потому что любая последовательность из двух различных цифр (по определению) чередуется. (например, 1,2 или 1,4 или 3,5);
• ${\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 само по себе чередуется.

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

В последовательности различных элементов подпоследовательность локальных экстремумов (элементов, больших, чем оба соседних элемента, или меньших, чем оба соседних элемента) образует каноническую самую длинную чередующуюся последовательность. Как следствие, самая длинная чередующаяся подпоследовательность последовательности $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}$, соответствующим образом центрированное и масштабированное, сходится к стандартному нормальному распределению.

Онлайн-алгоритмы

Проблема самой длинной чередующейся подпоследовательности также изучалась в рамках онлайн-алгоритмов , в которых элементы $\mathbf {x}$ представлены в онлайн-режиме, и лицу, принимающему решения, необходимо решить, включать или исключать каждый элемент в момент его первого представления, без каких-либо знаний об элементах, которые будут представлены в будущем,и без возможности вспомнить предыдущие наблюдения.

Учитывая последовательность $X_{1},X_{2},\ldots ,X_{n}$ независимых случайных величин с общим непрерывным распределением $F$, можно построить процедуру выбора, которая максимизирует ожидаемое количество чередующихся выборов. Такие ожидаемые значения можно точно оценить, и они равны $(2-{\sqrt {2}})n+O(1)$.

Как $n\rightarrow \infty$, оптимальное количество чередующихся онлайн-выборок, правильно центрированных и масштабированных, сходится к нормальному распределению.

См. также

• Попеременная перестановка
• Шаблон перестановки и избегание шаблона
• Подсчет локальных максимумов и/или локальных минимумов в заданной последовательности
• Поворотные тесты для проверки статистической независимости $n$ наблюдения
• Количество попеременных запусков
• Самая длинная возрастающая подпоследовательность
• Самая длинная общая подпоследовательность