188
правок
Изменения
м
Нет описания правки
{{Определение
|definition =
'''Наибольшая возрастающая подпоследовательность (НВП)''' (англ. ''Longest increasing subsequence'') строки <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> {{---}} наибольшее из возможных.
}}
<code>
'''vector<int>''' findLIS('''vector<int>''' a):
'''int''' n = a.size() ''<font color="green">//размер исходной последовательности</font>''
'''int''' prev[0..n - 1]
'''int''' d[0..n - 1]
== Решение за O(NlogN) ==
Для более быстрого решения данной задачи построим следующую динамику: пусть <tex>d[i](i = 0...n)</tex> {{---}} число, на которое оканчивается возрастающая последовательность длины <tex>i</tex>, а если таких чисел несколько {{---}} то наименьшее из них. Изначально мы предполагаем, что <tex>d[0] = -\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>i</tex>, а в <tex>prev[i]</tex> {{---}} позицию предыдущего элемента для <tex>a[i]</tex>.
<code>
'''vector<int>''' findLIS('''vector<int>''' a):
'''int''' n = a.size() ''<font color="green">//размер исходной последовательности</font>''
'''int''' d[0..n]
'''int''' pos[0..n]
|}
4. Берём элемент 2. Так как 2 < 9, то бинарным поиском находим нужную нам позицию <tex>z</tex>, такую, что <tex>t[i][z-1] \le leqslant 2 < t[i][z]</tex>. В данном случае это
первая позиция. Присваиваем <tex>t[i][z] = 2</tex> и проделываем такую же операцию, но для строки с индексом <tex>i+1</tex>.
