Изменения

|definition = Дана {{Acronym | перестановка | на самом деле может быть и мультиперестановкой }} <tex>\pi</tex> <tex>\{1, 2,~\dots,~n\}</tex> Найти . Требуется найти [[Задача о наибольшей возрастающей подпоследовательности | НВП]] <tex>\pi</tex> за <tex>O(n\operatorname{log}\operatorname{log}k)</tex>, где <tex>k</tex> - — длина НВП.

Пусть <tex>\pi(n)</tex> - — входная перестановка.

* Иначе <tex>\pi(i)</tex> становится лучшим элементом для такой длины <tex>l</tex>, что: {{Acronym | <tex>B[l]</tex> | предыдущее значение}}<tex> = \min \{ B[1..j] > \pi(i),~j < i \}</tex>

Следует отметить, что полученный массив также образует возрастающую последовательность, где мы должны выполнять операции <tex>insert, next, delete</tex>, соответственно целесообразно использовать [[ Приоритетные очереди | приоритетную очередь]], реализованную через [[Дерево ван Эмде Боаса]]. Таким образом получаем <tex>O(\operatorname{log}\operatorname{log} n)</tex> амортизированного временина одну операцию.

[[Файл:Operation1.jpg]] [[Файл:Operation2_1.jpg]] <tex>\longrightarrow</tex> [[Файл:Operation2_2.jpg]] {{Acronym |Последовательность:| именно она будет рассматриваться далее}}

! <tex>\pi_1</tex> || <tex>\pi_2</tex> || <tex>\pi_3</tex> || <tex>\pi_4</tex> || <tex>\pi_5</tex> || <tex>\pi_6</tex> || <tex>\pi_7</tex> || <tex>\pi_8</tex> || <tex>\pi_9</tex> || <tex>\pi_{10}</tex> || <tex>\pi_{11}</tex> || <tex>\pi_{12}</tex>

| 9 || 2 3 || 10 || 4 || 8 || 1 || 3 2 || 7 12 || 5 6 || 6 5 || 8 7 || 4 11

| style="background:#FFCC00"| 9 || || || || || style="background:#9886ff77A9F4"|9

| style="background:#FFCC00"| 2 3 || || || || || style="background:#9886ff77A9F4"|23

| 3 || style="background:#FFCC00"| 1 || 10 || || || || style="background:#9886ff77A9F4"|110

| 1 3 || style="background:#FFCC00"| 3 4 || || || || style="background:#9886ff77A9F4"|34

| 1 3 || 3 4 || style="background:#FFCC00"| 7 8 || || || style="background:#9886ff77A9F4"|78

| 1 || 3 || style="background:#FFCC00"| 5 1 || 4 || 8 || || || style="background:#9886ff77A9F4"|51

| 1 || 3 || 5 || style="background:#FFCC00"| 6 2 || 8 || || || style="background:#9886ff77A9F4"|62

| 1 || 3 2 || 5 || 6 8 || style="background:#FFCC00"| 8 12 || || style="background:#9886ff77A9F4"|812

| 1 || 3 2 || style="background:#FFCC00"| 4 6 || 12 || || style="background: #77A9F4"| 6 |-align="center" | 1 || 2 || style="background:#FFCC00"| 5 || 12 || || style="background: #77A9F4"| 5|-align="center" | 1 || 2 || 5 || style="background:#FFCC00"|7 | 8 | || style="background:#9886ff77A9F4"|47|-align="center" | 1 || 2 || 5 || 7 || style="background:#FFCC00"| 11 || style="background: #77A9F4"| 11

'''function''' LIS(<tex>\pi</tex>[]): int B = PriorityQueue()<font color=darkgreen>// рабочая приоритетная очередь</font> k = 0<font color=darkgreen>// длина НВП</font>

'''for''' i = 1..to n:

B.insert(x) <font color=darkgreen>// в любом случае добавляем в очередьочередной элемент</font> <font color=darkgreen>// устаревшие будем удалять</font> B.insert(x) '''if''' B.next(x) '''exists''' '''then''' B.delete(B.next(x)) <font color=darkgreen>// добавленный элемент — не максимальный</font> <font color=darkgreen>// удаляем предыдущее значение - — заменяем {{Acronym | следующий | минимальный из бОльшихбóльших}} </font> B.delete(B.next(x))

<font color=darkgreen>// добавленный элемент - максимальный</font> <font color=darkgreen>// предыдущие значения не трогаем, очередь увеличилась</font> k = k + 1 // добавляем максимальный - уже добавлен, ничего не удаляем

=== Расширение алгоритма на нахождение до нахождения НВП ===

Тогда, выбрав какой-нибудь лучший элемент для максимальной длины, мы можем легко {{Acronym | восстановить НВП | вообще говоря, не все НВП}}.==== Общий вид алгоритма ===={| class="wikitable" align="leftborder" style="color: black; background-color:#ffffcc;" cellpadding="10"|-align="center"! <tex>B_1</tex> || <tex>B_2</tex> || <tex>B_3</tex> || <tex>B_4</tex> || <tex>B_5</tex> || <tex>~\pi_i~</tex>|-align="center" | 9 || || || || || style="background: #77A9F4"| 9|-align="center" | 3 || || || || || style="background: #77A9F4"| 3|-align="center" | 3 || 10 || || || || style="background: #77A9F4"| 10|-align="center" | 3 || 4 || || || || style="background: #77A9F4"| 4|-align="center" | 3 || 4 || 8 || || || style="background: #77A9F4"| 8|-align="center" | style="background:#FFCC00"| 1 || 4 || 8 || || || style="background: #77A9F4"| 1|-align="center" | style="background:#FF7F00"|1 || style="background:#FFCC00"| 2 || 8 || || || style="background: #77A9F4"| 2|-align="center" | 1 || style="background:#FFCC00"|2 || 8 || 12 || || style="background: #77A9F4"| 12|-align="center" | 1 || style="background:#FFCC00"|2 || 6 || 12 || || style="background: #77A9F4"| 6|-align="center" | 1 || style="background:#FF7F00"|2 || style="background:#FFCC00"| 5 || 12 || || style="background: #77A9F4"| 5|-align="center" | 1 || 2 || style="background:#FF7F00"| 5 || style="background:#FFCC00"| 7 || || style="background: #77A9F4"| 7|-align="center" | 1 || 2 || 5 || style="background:#FF7F00"| 7 || style="background:#FF7F00"| 11 || style="background: #77A9F4"| 11 |} {| class="wikitable" align="leftborder" style="color: black; background-color:#ffffcc;" cellpadding="10"|-align="center"! colspan="12" | predecessor|-align="center"! 1 || 2 || 3 || 4 || 5 || 6 || 7 || 8 || 9 || 10 || 11 || 12 |-align="center"| || 1 || || 3 || 2 || 2 || 5 || 4 || || 3 || 7 || 8|}

'''function''' LIS(<tex>\pi</tex>[])[]

<font color = 'red'blue>predecessors predecessor = [n]</font> <font color=darkgreen>// резервируем <tex>n</tex> позиций</font>

<font color=blue>predecessor[x] = B.prev(x)</font> '''if''' B.next(x) '''exists''' '''then'''

<font color=darkgreen>//по цепочке от последнего элемента //восстанавливаем НВП</font> <font color=blue>result = []

'''return''' result</font>