Изменения

'''Наибольшая возрастающая подпоследовательность (НВП)''' (''англ. ''. 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 i_j \le 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>j = 0...i - 1)</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;

Для более быстрого решения данной задачи построим следующую динамику: пусть <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>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] = -INFINITY;INF '''for ''' i = 1...'''to''' n - 1 d[i] = INFINITY;INF '''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[pos]p]; reverse(answer); return answer;

Само табло представляет из себя расположение <tex>n_1</tex>+<tex>n_2</tex>+...+<tex>n_M</tex> различных целых чисел в массиве строк,выровненных по левому краю, где в ''<tex>i''-той </tex> строке содержится <tex>n_i</tex> элементов; при этом в каждой строке элементы возрастают слева направо, а элементы каждого столбца возрастают сверху вниз. Чтобы построить табло требуется прочитать очередной элемент ''a''<tex>a_i</tex>, если он больше либо равен <tex>n_j</tex>, где j {{-- -}} длина строки, то просто добавить в конец строки, если меньше, то требуется найти первый элемент ''<tex>b''</tex>, который больше данного ''a''<tex>a_i</tex>. Поставить элемент ''а'' <tex>a</tex> вместо ''<tex>b''</tex>. С элементом ''<tex>b'' </tex> требуется провести те же действия, что и с ''<tex>a''</tex>, только уже на ''<tex>i''+1 </tex> строке табла. Пример построения табла на массиве а (индексация ведётся от 0) :  а : 3,4,9,2,5,1

1 : Берём Пример построения табла на массиве <tex>a = [ 3, видим4, 9, что 3>02, который расположен на первой строке в ячейке с индексом ''j''=0. Увеличиваем ''j'' и в ''t[i5,j1 ]''=3</tex> :

t :{| border = 1; class="wikitable" |&nbsp;&nbsp;3&nbsp;&nbsp;|}

2 : . Берём элемент 4, видим. Видим, что 4>3. Увеличиваем ''<tex>j'' </tex> и в ''<tex>t[i,][j]''=4</tex>.

t :{| border = 1; class="wikitable" |&nbsp;&nbsp;3,&nbsp;&nbsp;|&nbsp;&nbsp;4&nbsp;&nbsp;|}

3 : . Аналогично с для элемента 9.

t :{| border = 1; class="wikitable" |&nbsp;&nbsp;3,&nbsp;&nbsp;|&nbsp;&nbsp;4,&nbsp;&nbsp;|&nbsp;&nbsp;9&nbsp;&nbsp;|}

4 : . Берём элемент 2. Так как 2<9, то бин. бинарным поиском находим нужную нам позицию ''<tex>z''</tex>, такую, что ''a<tex>t[i,][z-1]''<=\le 2<''at[i,][z]''</tex>. В данном случае это первая позиция. Ставим на место ''aПрисваиваем <tex>t[i,][z]'' = 2 </tex> и проделываем такую же операцию, как и но для 2, но на строке строки с индексом ''<tex>i''+1</tex>.

t :{| 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 : . Аналогично с для элемента 5.

t:{| 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 : . Аналогично для элемента 1.

t :{| 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;|}

==См. также==*[[Задача о наибольшей общей подпоследовательности]]*[[Наибольшая общая возрастающая подпоследовательность]]== Источники информации ==