Изменения

Перейти к: навигация, поиск

Участник:Artem.ustinov/НВП

19 байт добавлено, 16:14, 1 января 2018
Псевдокод
==== Псевдокод ====
<code>
'''int[]''' LIS(<tex>\pi</tex>[n]) '''PriorityQueue''' B '''int''' k = 0 <font color=blue>'''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) B.delete(B.next(x)) '''else''' k = k + 1 <font color=darkgreen>// по цепочке от последнего элемента // восстанавливаем НВП</font> <font color=blue>'''int''' result[k] '''int''' cur = B.max '''for''' i = k - 1 '''downto''' 0 result[i] = cur cur = predecessor[cur] '''return''' result</font></code>
== Оптимизация до O(n log log k) ==
76
правок

Навигация