Русская Википедия:Задача поиска наибольшей увеличивающейся подпоследовательности

Содержание

Текст

Текст

Текст

Текст

Текст

Текст

Текст

Текст

Текст

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

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

Подпоследовательность может и не являться подстрокой (то есть, её элементы не обязательно идут подряд в исходной последовательности). Формально, для строки x длины n необходимо найти максимальное число <math>l</math> и соответствующую ему возрастающую последовательность индексов <math>i_1 < i_2 < \ldots < i_l</math>, таких что <math>x[i_{k}] < x[i_{k+1}]\, \forall k \in {1, 2, \ldots, l-1}</math>. Наибольшая увеличивающая подпоследовательность имеет применения в физике, математике, теории представлений групп, теории случайных матриц. В общем случае известно решение этой задачи за время n log n в худшем случае случае.

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

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

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

Шаблон:Нет сносок Приведем алгоритм решения задачи, работающий за O(n log n).

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

 P = array of length N
 M = array of length N + 1
 L = 0
 for i in range 0 to N-1:
   lo = 1
   hi = L
   while lo ≤ hi:
     mid = ceil((lo+hi)/2)
     if X[M[mid]] < X[i]:
       lo = mid+1
     else:
       hi = mid-1
   newL = lo
   P[i] = M[newL-1]
   M[newL] = i
   if newL > L:
     L = newL
 S = array of length L
 k = M[L]
 for i in range L-1 to 0:
   S[i] = X[k]
   k = P[k]
 return S

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

Ссылки

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