47
правок
Изменения
м
Нет описания правки
* Если <tex>\pi(i)</tex> больше {{Acronym | <tex>\pi(1), \pi(2),~\dots~,\pi(i-1)</tex> | всех уже полученных значений B }}, значит с ним можно сделать максимальную, из уже рассмотренных, возрастающую подпоследовательность. Записываем его в конец <tex>B</tex>
* Иначе <tex>\pi(i)</tex> становится лучшим элементом для такой длины <tex>l</tex>заменяет наименьший лучший элемент, из тех, что: {{Acronym | <tex>B[l]</tex> | предыдущее значение}}больше <tex> = \min \{ B[1..j] > \pi(i) \}</tex> .
Следует отметить, что полученный массив также образует возрастающую последовательность, где мы должны выполнять операции <tex>insert, next, delete</tex>, соответственно целесообразно использовать [[ Приоритетные очереди | приоритетную очередь]], реализованную через [[Дерево ван Эмде Боаса]]. Таким образом получаем <tex>O(\operatorname{log}\operatorname{log} n)</tex> амортизированного времени на одну операцию.
==== Псевдокод ====
<code>
'''functionint''' LIS('''vector<int>''' <tex>\pi</tex>[]): int '''PriorityQueue''' B = PriorityQueue() <font color=darkgreen>// рабочая приоритетная очередь</font> '''int''' k = 0 <font color=darkgreen>// длина НВП</font> '''int''' n = <tex>\pi</tex>.size
'''for''' i = 1 to n
x = <tex>\pi</tex>[i]
<font color=darkgreen>// устаревшие будем удалять</font>
B.insert(x)
'''if''' <tex>\exists</tex> B.next(x) '''exists'''
<font color=darkgreen>// добавленный элемент — не максимальный</font>
<font color=darkgreen>// удаляем предыдущее значение — заменяем {{Acronym |следующий|минимальный из бóльших}}</font>
==== Псевдокод ====
<code>
'''functionvector<int>''' LIS('''vector<int>''' <tex>\pi</tex>[])[] '''PriorityQueue''' B = PriorityQueue() '''int''' k = 0 '''int''' n = <tex>\pi</tex>.size <font color=blue>'''vector<int>''' predecessor = [(n])</font> <font color=darkgreen>// резервируем <tex>n</tex> позиций</font>
'''for''' i = 1 to n
x = <tex>\pi</tex>[i]
B.insert(x)
<font color=blue>predecessor[x] = B.prev(x)</font>
'''if''' <tex>\exists</tex> B.next(x) '''exists'''
B.delete(B.next(x))
'''else'''
k = k + 1
<font color=darkgreen>//по цепочке от последнего элемента //восстанавливаем НВП</font> <font color=blue>'''vector<int>''' result = [] '''int''' cur = B.max()
result += [cur]
'''while''' <tex>\exists</tex> predecessor[cur] '''exists'''
result += [predecessor[cur]]
cur = predecessor[cur]
'''return''' result</font>
</code>
== Переименование Оптимизация до <tex>O(n\operatorname{log}\operatorname{log}k)</tex> ===== Деление на блоки ===
