Изменения

'''Наибольшая возрастающая подпоследовательность (НВП)''' (''англ. ''. 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>d</tex>, где <tex>d[i]</tex> <tex>{{---</tex> }} это длина наибольшей возрастающей подпоследовательности, оканчивающейся в элементе, с индексом <tex>i</tex>. Массив будем заполнять постепенно {{-- -}} сначала <tex>d[0]</tex>, потом <tex>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>a[j](j = 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(d[j]</tex>, для всех <tex>\limits_{j = 0...i - 1)}{d[j]}</tex> при условии, что <tex>a[j] < a[i]</tex>.

'''vector<int> Find''' findLIS('''vector<int> ''' a): '''int ''' n = a.size(); ''<font color="green">//размер исходной последовательности</font>'' vector< '''int> ''' prev([0..n);- 1] vector< '''int> ''' d([0..n);- 1] '''for ''' i = 0...'''to''' n - 1 d[i] = 1; p prev[i] = -1; '''for ''' j = 0...'''to''' i - 1 '''if ''' (a[j] < a[i] if '''and''' d[j] + 1 > d[i]) d[i] = d[j] + 1; prev[i] = j; int pos = 0 ''<font color="green">// индекс последнего элемента НВП</font>'' length = d[0], pos ''<font color= 0;"green">//length - длина наибольшей подпоследовательности, pos - последний символ наибольшей возрастающей подпоследовательностиНВП</font>'' '''for ''' i = 0...'''to''' n - 1 '''if ''' d[i] > length pos = i length = d[i]; pos ''<font color= i;"green">// восстановление ответа</font>'' '''vector<int> ''' answer; '''while ''' pos != -1 answer.push_back(a[pos]); pos = prev[pos]; reverse(answer); '''return ''' answer;

== Решение за O(NlogNN log N) ==Для более быстрого решения данной задачи построим следующую динамику: пусть <tex>d[i](i = 0...n)</tex> {{- --}} число, на которое оканчивается возрастающая последовательность длины <tex>i</tex>, а если таких чисел несколько {{- --}} то наименьшее из них. Изначально мы предполагаем, что <tex>d[0] = -</tex><tex>\infty</tex>, а все остальные элементы <tex>d[i] =</tex> <tex>\infty</tex>.Заметим два важных свойства этой динамики: <tex>d[i - 1]</tex> <tex>\le</tex> <tex>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>pos</tex> и <tex>prev</tex>. В <tex>pos[i]</tex> будем хранить позицию индекс элемента, на который заканчивается оптимальная подпоследовательность длины <tex>d[i]</tex> в <tex>a[i]</tex>, а в <tex>prev[i]</tex> {{--- }} позицию предыдущего элемента для <tex>a[i]</tex>. ===Псевдокод алгоритма===

'''vector<int> Find''' findLIS('''vector<int> ''' a): '''int ''' n = a.size(); int length ''<font color= 0; "green">//размер исходной последовательности</font>'' '''int ''' d[0..n], '''int''' pos[0..n], '''int''' prev[0..n- 1]; prev length = 0 pos[0] = -1; d[0] = <tex>-INFINITY;\infty</tex> '''for ''' i = 1...'''to''' n - 1 d[i] = INFINITY;<tex>\infty</tex> '''for ''' i = 0...'''to''' n - 1 int j = binsearchbinary_search(d[], a[i]); '''if ''' (d[j - 1] < a[i] '''and ''' a[i] < d[j]) d[j] = a[i]; pos[j] = i; prev[i] = pos[d[j - 1]]; length = max(length, j); ''<font color="green">// восстановление ответа</font>'' '''vector<int> ''' answer; int p = pos = [length;] '''while pos ''' p != -INFINITY 1 answer.push_back(a[prev[pos]p]); pos p = a[prev[posp]]; reverse(answer); '''return ''' answer;

== Ещё одно решение за О(NlogNN 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>n_1</tex>+<tex>n_2</tex>+...+<tex>n_M</tex> различных целых чисел в массиве строкa = [ 3, 4,выровненных по левому краю9, где в ''i''-той строке содержится <tex>n_i</tex> элементов; при этом в каждой строке элементы возрастают слева направо2, а элементы каждого столбца возрастают сверху вниз. Чтобы построить табло требуется прочитать очередной элемент ''a''5, если он больше либо равен <tex>n_j1 ]</tex>, где j - длина строки, то просто добавить в конец строки, если меньше, то требуется найти первый элемент ''b'', который больше данного ''a''. Поставить элемент ''а'' вместо ''b''. С элементом ''b'' требуется провести те же действия, что и с ''a'', только уже на ''i''+1 строке табла.:

Пример построения табла 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,4,9,2,5,1&nbsp;&nbsp;|}

1 : 2. Берём 3, видимэлемент <tex>4</tex>. Видим, что <tex>4 > 3</tex>0, который расположен на первой строке в ячейке с индексом ''j''=0. Увеличиваем ''<tex>j'' </tex> и в ''<tex>t[i,][j]''=34</tex>.

t = 3. Аналогично для элемента <tex>9</tex>.

2 : Берём 4, видим, что 4>{| border = 1; class="wikitable"|&nbsp;&nbsp;3. Увеличиваем ''j'' и в ''t[i,j]''=&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] = 32</tex> и проделываем такую же операцию,4но для строки с индексом <tex>i+1</tex>.

3 : Аналогично с {| 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;|}

4 : Берём {| border = 1; class="wikitable"|-align = "center"|&nbsp;&nbsp;2. 2<9, то бин. поиском находим нужную нам позицию ''z'', такую, что ''a[i,z&nbsp;&nbsp;|&nbsp;&nbsp;4&nbsp;&nbsp;|&nbsp;&nbsp;5&nbsp;&nbsp;|-1]''<align =2<''a[i,z]''. В данном случае это "center"|&nbsp;&nbsp;3&nbsp;&nbsp;|&nbsp;&nbsp;9&nbsp;&nbsp;первая позиция. Ставим на место ''a[i,z]'' 2 и проделываем такую же операцию, как и для 2, но на строке с индексом ''i''+1.|}

5 : Аналогично с {| 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;|}

t= 2Таким образом,4длина наибольшей возрастающей подпоследовательности для массива <tex>a</tex> равна <tex>3</tex> (например,5 подпоследовательность из элементов <tex>[ 3, 4,9]</tex>).

t == См. также ==*[[Задача о наибольшей общей подпоследовательности]] 1,4,5*[[Наибольшая общая возрастающая подпоследовательность]] 2,9*[[Задача о наибольшей общей палиндромной подпоследовательности]] 3==Примечания==

При построении нам потребуется лишь первая строка<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)]