Возрастающая подпоследовательность

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

Постановка задачи

Отметим, подпоследовательность может и не являться подстрокой. Формально, для строки x длины n необходимо найти максимальное число l и соответствующую ему возрастающую последовательность индексов i₁..i_l, таких что $x[i_{k}] < x[i_{k+1}]\,\forall {k}\,\mathcal{2}{\,1\,..\,n-1}$. Наибольшая увеличивающая подпоследовательность имеет применения в физике, математике, теории представления групп, теории случайных матриц. В общем случае известно решение этой задачи за время n log n^[1] в худшем случае.

Родственные алгоритмы

• Задача наибольшей увеличивающейся подпоследовательности схожа с задачей поиска наибольшей общей подпоследовательности, имеющей квадратичное динамическое решение.
• В частном случае, если строка является перестановкой 1..n, задача имеет решение за n log log n^[2] с использованием деревьев ван Эмд Босса.
• При использовании дерева, построенного для элементов алфавита, возможно решение задачи за O( n log A ), где A - мощность алфавита, определяемая заранее. При реализации сбалансированными деревьями, необязательно задавать A наперёд. По очевидным причинам A ограничивается длиной строки.
• Возможно также свести задачу к поиску длиннейшего пути в ориентированном ациклическом графе, задавая рёбра между возрастающими элементами. Хотя подсчёт длиннейшего пути будет занимать линейное время от числа рёбер, в худшем случае оно может быть квадратично от длины строки.

Пример эффективного алгоритма

Для строки x будем хранить массивы M и P длины n. M[i] содержит наименьший по величине из последних элементов возрастающих подпоследовательностей x_nj длины i, $(\mathcal{8}j\,\mathcal{2}\,1\,..\,i:x[n_{j}] \le\,M[i])$, найденных на данном шаге. P[i] хранит индекс предшествующего символа для наидлиннейшей возрастающей подпоследовательности, оканчивающейся в i-й позиции. На каждом шаге будем хранить текущий максимум длины подпоследовательности и соответствующий индекс конечного символа, не забывая поддерживать свойства массивов. Шаг представляет из себя переход к следующему элементу строки, для каждого перехода потребуется не более логарифма времени (бинарный поиск по массиву M).

l = index = M[0] = 0
for i = 1 to n
   бинарный поиск наибольшего индекса j ≤ l, удовлетворяющего X[M[j]] < X[i]
   P[i] = M[j]
   if j == l or X[i] < X[M[j+1]] // нашли более оптимальную подпоследовательность
      M[j+1] = i
      l = max{l, j+1}

Очевидно, после выполнения алгоритма, l — длина искомой подпоследовательности, сами же элементы можно получить, разворачивая P рекурсивно из элемента index.

См. также

1. ↑ Schensted, C. (1961). «Longest increasing and decreasing subsequences». Canadian Journal of Mathematics 13: 179—191.
2. ↑ [1]Hunt, J.; Szymanski, T. (1977). «A fast algorithm for computing longest common subsequences». Communications of the ACM: 350—353.

Ссылки

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