Изменения

'''Наибольшая возрастающая подпоследовательность (НВП)''' (''англ. ''. Longest increasing subsequence - , LIS'') строки <tex> x </tex> длины <tex> n </tex> {{--- }} это последовательность <tex> x[i_1] < x[i_2] < \dots < x[i_k] </tex> символов строки <tex> x </tex> таких, что <tex> i_1 < i_2 < \dots < i_k, 1 \le leqslant i_j \le leqslant n </tex>, причем <tex> k </tex> {{--- }} наибольшее из возможных.

Задача заключается в том, чтобы отыскать это наибольшее <tex> k </tex> и саму подпоследовательность.Известно несколько алгоритмов решения этой задачи.__TOC__==== Пример алгоритма, работающего Решение за время O(N<texsup> O(n^2) </texsup> ==) ==Строим таблицу Построим массив <tex> a[1 \dots n] d</tex>. Каждый её элемент , где <tex> ad[i] </tex> {{-- -}} это длина наибольшей возрастающей подпоследовательности, оканчивающейся точно в позиции элементе, с индексом <tex> i </tex>. Если мы построим эту таблицуМассив будем заполнять постепенно {{---}} сначала <tex>d[0]</tex>, то ответ к задаче - наибольшее число потом <tex>d[1]</tex> и т.д. Ответом на нашу задачу будет максимум из этой таблицывсех элементов массива <tex>d</tex>.Само построение тоже элементарноЗаполнение массива будет следующим: если <tex> ad[i] = \max{(1</tex>, то искомая последовательность состоит только из числа <tex>a[ji]</tex>. Если <tex>d[i] + > 1)} </tex>,для всех то перед числом <tex>a[i]</tex> в подпоследовательности стоит какое-то другое число. Переберем его: это может быть любой элемент <tex> a[j](j = 1\dots 0...i-1)</tex>, для которых но такой, что <tex> xa[j] < xa[i]</tex>. Пусть на каком-то шаге нам надо посчитать очередное <tex>d[i] </tex>. База динамики Все элементы массива <tex> ad</tex> до него уже посчитаны. Значит наше <tex>d[i]</tex> мы можем посчитать следующим образом: <tex>d[i] = 1] + \max\limits_{j = 0 .. i - 1 }{d[j]}</tex> при условии, что <tex>a[j] < a[i]</tex>.Если Пока что мы хотим восстановить нашли лишь максимальную длину наибольшей возрастающей подпоследовательности, но саму подпоследовательность, то ее мы вывести не можем. Для восстановления ответа заведем массив предыдущих величин <tex>prev[0...n - 1]</tex> такой, что где <tex>prev[i]</tex> - предпоследний элемент будет означать индекс в НВПмассиве <tex>a[]</tex>, оканчивающейся в элементе с номером при котором достигалось наибольшее значение <tex> d[i ]</tex>. Его значение будет изменяться вместе Для вывода ответа будем идти от элемента с изменением соответствующего i-ого элемента матрицы максимальным значениям <tex>ad[i]</tex>по его предкам. ===Псевдокод алгоритма===

lis '''vector<int>''' findLIS('''vector<int>''' a): '''int''' n = 0 // длина НВП a .size ''<font color= (n, 0) "green">//размер исходной последовательности</ заполняем нулямиfont>'' '''int''' prev = ([0..n, -1) // ] '''int''' d[0..n -1 ] '''for''' i = 0 '''to''' n - признак отсутствия предпоследнего элемента, что указывает на то, что данный элемент является первым в подпоследовательности1 a d[1i] = 1 For prev[i ] = 2 to n-1 For '''for''' j = 1 0 '''to ''' i - 1 If '''if''' (xa[ij] > x< a[ji]) '''and (a''' d[j] + 1 > ad[i]) // нашли более оптимальную подпоследовательность a d[i] = ad[j]+1 prev[i] = j lis pos = 0 ''<font color="green">// индекс последнего элемента НВП</font>'' length = d[0] ''<font color="green">// длина НВП</font>'' '''for''' i = 0 '''to''' n - 1 '''if''' d[i] > length pos = i length = maxd[i] ''<font color="green">// восстановление ответа</font>'' '''vector<int>''' answer '''while''' pos != -1 answer.push_back(lis, a[ipos]) pos = prev[pos] reverse(answer) '''return''' answer

== Решение за O(N log N) ==Для вывода самой подпоследовательности достаточной пройти по массиву более быстрого решения данной задачи построим следующую динамику: пусть <tex>prevd[i](i = 0...n)</tex>{{---}} число, начиная с номера того элементана которое оканчивается возрастающая последовательность длины <tex>i</tex>, на котором а если таких чисел несколько {{---}} то наименьшее из них. Изначально мы зафиксировали наш ответ lisпредполагаем, и спускаясь по его предыдущим элементамчто <tex>d[0] = -\infty</tex>, пока не достигнем а все остальные элементы <tex>d[i] =</tex> <tex>\infty</tex>.Заметим два важных свойства этой динамики: <tex>d[i -1 ] \leqslant d[i]</tex>, для всех <tex>i = 1...n</tex> и каждый элемент <tex>a[i]</tex> обновляет максимум один элемент <tex>d[j]</tex>. Это означает, что при обработке очередного <tex>a[i]</tex>, мы можем за <tex> O(\log n) </tex> c помощью [[Целочисленный_двоичный_поиск|двоичного поиска]] в предке очередного элементамассиве <tex>d</tex> найти первое число, которое больше либо равно текущего <tex>a[i]</tex> и обновить его.

==== Пример алгоритма, работающего за время <tex> O(n\cdot\log n) </tex> ====Для строки ''x'' восстановления ответа будем по-прежнему хранить массивы <tex>a</tex> (поддерживать заполнение двух массивов: <tex>apos</tex> уже длины n + 1) и <tex>predprev</tex>, добавим к ним так же массив no из n + 1 элементов так, что в no[i] хранится номер последнего элемента в возрастающей подпоследовательности длины i. Теперь В <tex> apos[i] </tex> содержит наименьший по величине элементбудем хранить индекс элемента, на который может оканчиваться возрастающая заканчивается оптимальная подпоследовательность длины <tex>i</tex>, среди всех а в <tex>xprev[ji]</tex>, где <tex>1 \leqslant j \leqslant i{{-1 </tex>, если мы на шаге <tex>i</tex>. В свою очередь, pred[i] хранит индекс предшевствующего символа для наибольшей возрастающей подпоследовательности, оканчивающейся в i-й позиции. Заметим, что <tex> a[0] < a[1] < a[2] < \dots < a[n] </tex>. Пусть мы находимся на i-ом шаге, тогда нам надо найти такой номер k <tex> a[k] \leqslant x[i] < a[k+1] </tex> (если положить при начальной реализации <tex> a[0] = -\inf, a[1] = a[2] = \dots = a[n] = \inf </tex>, то такое k всегда найдется).Причем если в условии не строгое возрастание, то массив }} позицию предыдущего элемента для <tex>a</tex> ''не убывает'', и надо искать наибольшее k из возможных. После этого полагаем <tex> a[k + 1] = x[i] </tex>, а остальные элементы массива не меняем. В силу упорядоченности массива a, мы можем искать k бинарным поиском (при не строгом возрастании необходимо пользоваться функцией upper_bound(1, n, a[i])). Параллельно нахождению НВП будем записывать массив предков pred и номеров no. Подсчитаем время: мы n раз выпоняем бинарный поиск, что требует <tex> O(\log n) </tex> времени. Итого: <tex> O(n\cdot\log n) </tex>.

lis '''vector<int>''' findLIS('''vector<int>''' a): '''int''' n = a.size ''<font color= "green">//размер исходной последовательности</font>'' '''int''' d[0..n] a = ( '''int''' pos[0..n + 1, inf)] pred = ( '''int''' prev[0..n, -1)] length = 0 a pos[0] = -inf1 no d[0] = <tex>-1 \infty</tex> For '''for''' i = 1 '''to ''' n d[i] = <tex>\infty</tex> '''for''' i = 0 '''to''' n - 1 j = binary_search(0d, n, xa[i]) // бинарный поиск j < i, удовлетворяющего x[a '''if''' (d[j]- 1] < xa[i] и x'''and''' a[i] < x[ad[j + 1]]) d[j + 1] = a[i] p pos[j] = i prev[i] = nopos[j- 1] length = max(length, j) no ''<font color="green">// восстановление ответа</font>'' '''vector<int>''' answer p = pos[j + length] '''while''' p != -1 answer.push_back(a[p] ) p = i;prev[p] If reverse(lis < j + 1answer) lis = j + 1; '''return''' answer

== Ещё одно решение за О(N log N) ==Существует ещё одно решение, которое позволяет нам найти длину наибольшей возрастающей подпоследовательности, но без возможности восстановления данной подпоследовательности. Для этого мы воспользуемся таблом Юнга. Оно обладает таким свойством, что длина первой строки табла и будет являться искомой величиной<ref>[https://en.wikipedia.org/wiki/Robinson%E2%80%93Schensted_correspondence#Properties Wikipedia {{---}} Robinson–Schensted correspondence]</ref>. Само табло представляет из себя расположение <tex>n_1+n_2+...+n_M</tex> различных целых чисел в массиве строк, выровненных по левому краю, где в <tex>i</tex> строке содержится <tex>n_i</tex> элементов; при этом в каждой строке элементы возрастают слева направо, а элементы каждого столбца возрастают сверху вниз. Чтобы построить табло требуется прочитать очередной элемент <tex>a_i</tex>, если он больше либо равен <tex>n_j</tex>, где <tex>j</tex> {{---}} длина строки, то просто добавить в конец строки, если меньше, то требуется найти первый элемент <tex>b</tex>, который больше данного <tex>a_i</tex>. Поставить элемент <tex>a</tex> вместо <tex>b</tex>. С элементом <tex>b</tex> требуется провести те же действия, что и с <tex>a</tex>, только уже на <tex>i+1</tex> строке табла. Пример построения табла на массиве <tex>a = [ 3, 4, 9, 2, 5, 1 ]</tex> : 1. Берём элемент <tex>3</tex>. Видим, что <tex>3 > 0</tex>, который расположен на первой строке в ячейке с индексом <tex>j = 0</tex>. Увеличиваем <tex>j</tex> и <tex>t[i][j] = 3</tex>. :{| border = 1; class="wikitable"|&nbsp;&nbsp;3&nbsp;&nbsp;|} 2. Берём элемент <tex>4</tex>. Видим, что <tex>4 > 3</tex>. Увеличиваем <tex>j</tex> и <tex>t[i][j] = 4</tex>. :{| border = 1; class="wikitable"|&nbsp;&nbsp;3&nbsp;&nbsp;|&nbsp;&nbsp;4&nbsp;&nbsp;|} 3. Аналогично для элемента <tex>9</tex>. :{| border = 1; class="wikitable"|&nbsp;&nbsp;3&nbsp;&nbsp;|&nbsp;&nbsp;4&nbsp;&nbsp;|&nbsp;&nbsp;9&nbsp;&nbsp;|} 4. Берём элемент <tex>2</tex>. Так как <tex>2 < 9</tex>, то бинарным поиском находим нужную нам позицию <tex>z</tex>, такую, что <tex>t[i][z-1] \leqslant 2 < t[i][z]</tex>. В данном случае это первая позиция. Присваиваем <tex>t[i][z] = 2</tex> и проделываем такую же операцию, но для строки с индексом <tex>i+1</tex>. :{| border = 1; class="wikitable"|-align = "center"|&nbsp;&nbsp;2&nbsp;&nbsp;|&nbsp;&nbsp;4&nbsp;&nbsp;|&nbsp;&nbsp;9&nbsp;&nbsp;|-align = "center"|&nbsp;&nbsp;3&nbsp;&nbsp;|} 5. Аналогично для элемента <tex>5</tex>. :{| border = 1; class="wikitable"|-align = "center"|&nbsp;&nbsp;2&nbsp;&nbsp;|&nbsp;&nbsp;4&nbsp;&nbsp;|&nbsp;&nbsp;5&nbsp;&nbsp;|-align = "center"|&nbsp;&nbsp;3&nbsp;&nbsp;|&nbsp;&nbsp;9&nbsp;&nbsp;|} 6. Аналогично для элемента <tex>1</tex>. :{| border = 1; class="wikitable"|-align = "center"|&nbsp;&nbsp;1&nbsp;&nbsp;|&nbsp;&nbsp;4&nbsp;&nbsp;|&nbsp;&nbsp;5&nbsp;&nbsp;|-align = "center"|&nbsp;&nbsp;2&nbsp;&nbsp;|&nbsp;&nbsp;9&nbsp;&nbsp;|-align = "center"|&nbsp;&nbsp;3&nbsp;&nbsp;|} Таким образом, длина наибольшей возрастающей подпоследовательности для массива <tex>a</tex> равна <tex>3</tex> (например, подпоследовательность из элементов <tex>[ 3, 4, 9 ]</tex>).  == См. также ==*[[Задача о наибольшей общей подпоследовательности]]*[[Наибольшая общая возрастающая подпоследовательность]]*[[Задача о наибольшей общей палиндромной подпоследовательности]]==Примечания== <references />== Источники информации ==* [http://ru.wikipedia.org/wiki/LIS Википедия {{---}} Задача поиска наибольшей увеличивающейся подпоследовательности]* [https://en.wikipedia.org/wiki/Longest_increasing_subsequence Wikipedia {{---}} Longest increasing subsequence]* [http://informatics.mccme.ru/moodle/mod/book/view.php?id=488 Дистанционная подготовка {{---}} Наибольшая возрастающая подпоследовательность (НВП, Longest Increasing Subsequence, LIS)]* [http://e-maxx.ru/algo/longest_increasing_subseq_log #7 MAXimal :: algo :: Длиннейшая возрастающая подпоследовательность за O (N log N)]* [[Категория:Дискретная математика и алгоритмы]][[httpКатегория://ru.wikipedia.org/wiki/LIS Задача поиска наибольшей увеличивающейся подпоследовательностиДинамическое программирование]]