Изменения

'''Наибольшая возрастающая подпоследовательность (НВП)''' (''англ. ''. 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> {{--- }} наибольшее из возможных.

Задача заключается __TOC__== Решение за время O(N²) ==Построим массив <tex>d</tex>, где <tex>d[i]</tex> {{---}} это длина наибольшей возрастающей подпоследовательности, оканчивающейся в томэлементе, с индексом <tex>i</tex>. Массив будем заполнять постепенно {{---}} сначала <tex>d[0]</tex>, чтобы отыскать это наибольшее потом <tex> k d[1]</tex> и саму подпоследовательностьт.д.Известно несколько алгоритмов решения этой задачиОтветом на нашу задачу будет максимум из всех элементов массива <tex>d</tex>.Заполнение массива будет следующим: если <tex>d[i] ==== Пример алгоритма1</tex>, то искомая последовательность состоит только из числа <tex>a[i]</tex>. Если <tex>d[i] > 1</tex>, работающего за время то перед числом <tex>a[i]</tex> в подпоследовательности стоит какое-то другое число. Переберем его: это может быть любой элемент <tex> Oa[j](n^2j = 0...i - 1) </tex> ====Строим таблицу , но такой, что <tex> a[j] < a[i]</tex>. Пусть на каком-то шаге нам надо посчитать очередное <tex>d[i]</tex>. Все элементы массива <tex>d</tex> до него уже посчитаны. Значит наше <tex>d[i]</tex> мы можем посчитать следующим образом: <tex>d[i] = 1 + \max\dots nlimits_{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>. Если мы построим эту таблицу, то ответ к задаче - наибольшее число из этой таблицыДля вывода ответа будем идти от элемента с максимальным значениям <tex>d[i]</tex> по его предкам.Само построение тоже элементарно===Псевдокод алгоритма===<code> '''vector<int>''' findLIS('''vector<int>''' a): , '''int''' n = a.size ''<font color="green">//размер исходной последовательности<tex/font> a'' '''int''' prev[0..n - 1] '''int''' d[0..n - 1] '''for''' i = 0 '''to''' n - 1 d[i] = 1 prev[i] = \max{-1 '''for''' j = 0 '''to''' i - 1 '''if''' (a[j] < a[i] '''and''' d[j] + 1> d[i])} d[i] = d[j] + 1 prev[i] = j pos = 0 ''<font color="green">// индекс последнего элемента НВП</texfont>'' length = d[0] ''<font color="green">,для всех // длина НВП<tex/font> j '' '''for''' i = 0 '''to''' n - 1\dotsi '''if''' d[i] > length pos = i length = d[i] ''<font color="green">// восстановление ответа</font>'' '''vector<int>''' answer '''while''' pos != -1 answer.push_back(a[pos]) pos = prev[pos] reverse(answer) '''return''' answer </code>== Решение за O(N log N) ==Для более быстрого решения данной задачи построим следующую динамику: пусть <tex>d[i](i = 0...n)</tex> {{---}} число, на которое оканчивается возрастающая последовательность длины <tex>i</tex>, а если таких чисел несколько {{---}} то наименьшее из них. Изначально мы предполагаем, для которых что <tex> xd[j0] = -\infty< x/tex>, а все остальные элементы <tex>d[i] =</tex> <tex>\infty</tex>. База Заметим два важных свойства этой динамики : <tex> ad[i - 1] \leqslant d[i]</tex>, для всех <tex>i = 1 ...n</tex> и каждый элемент <tex>a[i]</tex> обновляет максимум один элемент <tex>d[j]</tex>.Если мы хотим восстановить саму подпоследовательность, то заведем массив предыдущих величин pred такойЭто означает, что predпри обработке очередного <tex>a[i] - предпоследний элемент </tex>, мы можем за <tex> O(\log n) </tex> c помощью [[Целочисленный_двоичный_поиск|двоичного поиска]] в НВПмассиве <tex>d</tex> найти первое число, оканчивающейся в элементе с номером которое больше либо равно текущего <tex> a[i ]</tex>и обновить его. Его значение будет изменяться вместе с изменением соответствующего  Для восстановления ответа будем поддерживать заполнение двух массивов: <tex>pos</tex> и <tex>prev</tex>. В <tex>pos[i]</tex> будем хранить индекс элемента, на который заканчивается оптимальная подпоследовательность длины <tex>i</tex>, а в <tex>prev[i]</tex> {{---ого }} позицию предыдущего элемента матрицы для <tex>a[i]</tex>. ===Псевдокод алгоритма===

lis '''vector<int>''' findLIS('''vector<int>''' a): '''int''' n = 0 a.size ''<font color="green">//размер исходной последовательности</ длина НВПfont>'' a = { '''int''' d[0..n] '''int''' pos[0} // заполняем нулями..n] pred = {-1 '''int''' prev[0..n -1} // ] length = 0 pos[0] = -1 - признак отсутствия предпоследнего элемента, что указывает на то, что данный элемент является первым в подпоследовательности a d[10] = 1; <tex>-\infty</tex> For '''for''' i = 2 1 '''to ''' n For j d[i] = <tex>\infty</tex> '''for''' i = 1 0 '''to i ''' n - 1 If j = binary_search(xd, a[i] > x) '''if''' (d[j- 1]) and (< a[ji] + 1 > '''and''' a[i] < d[j]) // нашли более оптимальную подпоследовательность d[j] = a[i] = a pos[j]+1;= i pred prev[i] = pos[j; - 1] length = max(length, j) lis ''<font color= "green">// восстановление ответа</font>'' '''vector<texint>\max{''' answer p = pos[length] '''while''' p != -1 answer.push_back(a[ip]}, i ) p = 1\dotsn</tex>, prev[p] reverse(answer) '''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> различных целых чисел в массиве строк, выровненных по массиву predлевому краю, где в <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>, на котором мы зафиксировали наш ответ lisто бинарным поиском находим нужную нам позицию <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> (max^nнапример, подпоследовательность из элементов <tex>[ 3, 4, 9 ]</tex>)_1 .  == См. также ==*[[Задача о наибольшей общей подпоследовательности]]*[[Наибольшая общая возрастающая подпоследовательность]]*[[Задача о наибольшей общей палиндромной подпоследовательности]]==Примечания== <references /tex>== Источники информации ==* [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)] [[Категория:Дискретная математика и алгоритмы]][[Категория:Динамическое программирование]]