Главная
Новости
Строительство
Ремонт
Дизайн и интерьер

















Яндекс.Метрика

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

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

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

Отметим, подпоследовательность может и не являться подстрокой (то есть, её элементы не обязательно идут подряд в исходной последовательности). Формально, для строки x длины n необходимо найти максимальное число l и соответствующую ему возрастающую последовательность индексов i 1 < i 2 < … < i l {displaystyle i_{1}<i_{2}<ldots <i_{l}} , таких что x [ i k ] < x [ i k + 1 ] ∀ k 2 1 . . l − 1 {displaystyle x[i_{k}]<x[i_{k+1}],forall {k},{mathcal {2}}{,1,..,l-1}} . Наибольшая увеличивающая подпоследовательность имеет применения в физике, математике, теории представления групп, теории случайных матриц. В общем случае известно решение этой задачи за время 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] содержит индекс наименьшего по величине из последних элементов возрастающих подпоследовательностей xnj длины i, ( 8 j 2 1 . . i : x [ n j ] ≤ M [ i ] ) {displaystyle ({mathcal {8}}j,{mathcal {2}},1,..,i:x[n_{j}]leq ,M[i])} , найденных на данном шаге. 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.