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

02.10.2022


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

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

x i 1 > x i 2 < x i 3 > … x i k ∧ 1 ≤ i 1 < i 2 < … < i k ≤ n . {displaystyle x_{i_{1}}>x_{i_{2}}<x_{i_{3}}>ldots x_{i_{k}}qquad land qquad 1leq i_{1}<i_{2}<ldots <i_{k}leq n.}

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

x i 1 < x i 2 > x i 3 < … x i k ∧ 1 ≤ i 1 < i 2 < … < i k ≤ n . {displaystyle x_{i_{1}}<x_{i_{2}}>x_{i_{3}}<ldots x_{i_{k}}qquad land qquad 1leq i_{1}<i_{2}<ldots <i_{k}leq n.}

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

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

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

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

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

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

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

E [ A n ] = 2 n 3 + 1 6 and Var ⁡ [ A n ] = 8 n 45 − 13 180 . {displaystyle E[A_{n}]={frac {2n}{3}}+{frac {1}{6}}qquad { ext{and}}qquad operatorname {Var} [A_{n}]={frac {8n}{45}}-{frac {13}{180}}.}

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