Быстрый поиск наибольшей возрастающей подпоследовательности

Эта статья находится в разработке!

Задача:

Дана перестановка [math]\pi[/math] [math]\{1, 2,~\dots,~n\}[/math] Найти НВП [math]\pi[/math] за [math]O(n\operatorname{log}\operatorname{log}k)[/math], где [math]k[/math] - длина НВП.

Алгоритм [math]O(n\operatorname{log}\operatorname{log}n)[/math]

Нахождение длины НВП

Основная идея

Пусть [math]\pi(n)[/math] - входная перестановка.

Для каждой длины [math]l = 1, 2, \dots[/math] предполагаемой НВП находим наименьший элемент, что может быть последним в возрастающей подпоследовательности длины [math]l[/math], запишем их в массив [math]B[l][/math].

Если обрабатываемый элемент [math]\pi(i)[/math] больше последнего элемента какой-нибудь возрастающей последовательности, он может ее увеличить.

Будем последовательно обрабатывать элементы [math]\pi(1), \pi(2),~\dots,~\pi(n)[/math]:

• Если [math]\pi(i)[/math] больше [math]\pi(1), \pi(2),~\dots~,\pi(i-1)[/math] , значит с ним можно сделать максимальную, из уже рассмотренных, возрастающую подпоследовательность. Записываем его в конец [math]B[/math]
• Иначе [math]\pi(i)[/math] становится лучшим элементом для такой длины [math]l[/math], что: [math]B[l][/math] [math] = \min \{ B[j] \gt \pi(i),~j \lt i \}[/math]

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

Пример

Типы операций:

Последовательность:

[math]\pi_1[/math]	[math]\pi_2[/math]	[math]\pi_3[/math]	[math]\pi_4[/math]	[math]\pi_5[/math]	[math]\pi_6[/math]	[math]\pi_7[/math]	[math]\pi_8[/math]	[math]\pi_9[/math]
9	2	1	3	7	5	6	8	4

Состояние очереди при каждом добавлении:

[math]B_1[/math]	[math]B_2[/math]	[math]B_3[/math]	[math]B_4[/math]	[math]B_5[/math]	[math]~\pi_i~[/math]
9					9
2					2
1					1
1	3				3
1	3	7			7
1	3	5			5
1	3	5	6		6
1	3	5	6	8	8
1	3	4	6	8	4

Псевдокод

   function LIS([math]\pi[/math][])
       B = PriorityQueue()
       k = 0
       n = [math]\pi[/math].size
       for i = 1..n:
           x = [math]\pi[/math][i]
           B.insert(x)             // в любом случае добавляем в очередь
           if B.next(x) exists then
               B.delete(B.next(x)) // удаляем предыдущее значение - заменяем  следующий  
           else
               k = k + 1           // добавляем максимальный - уже добавлен, ничего не удаляем
       return k

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

Основная идея

Будем запоминать пары: для каждого элемента записываем его "предшественника".

Тогда, выбрав какой-нибудь лучший элемент для максимальной длины, мы можем легко восстановить все НВП.

Псевдокод

   function LIS([math]\pi[/math][])
       B = priorityQueue()
       k = 0
       n = [math]\pi[/math].size
       <color = 'red'>predecessors = [n]</color>
       for i = 1 to n
           x = [math]\pi[/math][i]
           B.insert(x)
           predecessor[x] = B.prev(x)
           if B.next(x) exists then
               B.delete(B.next(x))
           else
               k = k + 1
       result = []
       cur = B.max()
       result += [cur]
       while predecessor[cur] exists
           result += [predecessor[cur]]
           cur = predecessor[cur]
       return result