Задача поиска наибольшей увеличивающейся подпоследовательности состоит в нахождении наиболее длинной возрастающей подпоследовательности в данной последовательности элементов.
Отметим, подпоследовательность может и не являться подстрокой (то есть, её элементы не обязательно идут подряд в исходной последовательности). Формально, для строки x длины n необходимо найти максимальное число l и соответствующую ему возрастающую последовательность индексов , таких что . Наибольшая увеличивающая подпоследовательность имеет применения в физике, математике, теории представления групп, теории случайных матриц. В общем случае известно решение этой задачи за время n log n в худшем случае[1].
В этой статье или разделе имеется список источников или внешних ссылок, но источники отдельных утверждений остаются неясными из-за отсутствия сносок. |
Приведем алгоритм решения задачи, работающий за O(n log n).
Для строки x будем хранить массивы M и P длины n. M[i] содержит индекс наименьшего по величине из последних элементов возрастающих подпоследовательностей xnj длины 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.
Данная страница на сайте WikiSort.ru содержит текст со страницы сайта "Википедия".
Если Вы хотите её отредактировать, то можете сделать это на странице редактирования в Википедии.
Если сделанные Вами правки не будут кем-нибудь удалены, то через несколько дней они появятся на сайте WikiSort.ru .