Быстрый поиск наибольшей возрастающей подпоследовательности
Эта статья находится в разработке!
Задача: |
Дана перестановка . Требуется найти НВП за , где — длина НВП. |
Алгоритм
Нахождение длины НВП
Основная идея
Пусть
— входная перестановка.Для каждой длины элемент, что может быть последним в возрастающей подпоследовательности длины , запишем их в массив .
предполагаемой НВП находим наименьшийЕсли обрабатываемый элемент
больше последнего элемента какой-нибудь возрастающей последовательности, он может ее увеличить.Будем последовательно обрабатывать элементы
:- Если , значит с ним можно сделать максимальную, из уже рассмотренных, возрастающую подпоследовательность. Записываем его в конец больше
- Иначе становится лучшим элементом для такой длины , что:
Следует отметить, что полученный массив также образует возрастающую последовательность, где мы должны выполнять операции приоритетную очередь, реализованную через Дерево ван Эмде Боаса. Таким образом получаем амортизированного времени на одну операцию.
, соответственно целесообразно использоватьПример
Типы операций:
Последовательность:
9 | 3 | 10 | 4 | 8 | 1 | 2 | 12 | 6 | 5 | 7 | 11 |
Состояние очереди при каждом добавлении:
9 | 9 | ||||
3 | 3 | ||||
3 | 10 | 10 | |||
3 | 4 | 4 | |||
3 | 4 | 8 | 8 | ||
1 | 4 | 8 | 1 | ||
1 | 2 | 8 | 2 | ||
1 | 2 | 8 | 12 | 12 | |
1 | 2 | 6 | 12 | 6 | |
1 | 2 | 5 | 12 | 5 | |
1 | 2 | 5 | 7 | 7 | |
1 | 2 | 5 | 7 | 11 | 11 |
Псевдокод
function LIS(следующий B.delete(B.next(x)) else // добавленный элемент - максимальный // предыдущие значения не трогаем, очередь увеличилась k = k + 1 return k[]): int B = PriorityQueue() // рабочая приоритетная очередь k = 0 // длина НВП n = .size for i = 1 to n x = [i] // в любом случае добавляем в очередь очередной элемент // устаревшие будем удалять B.insert(x) if B.next(x) exists // добавленный элемент — не максимальный // удаляем предыдущее значение — заменяем
Расширение алгоритма до нахождения НВП
Основная идея
Будем запоминать пары: для каждого элемента записываем его "предшественника".
Тогда, выбрав какой-нибудь лучший элемент для максимальной длины, мы можем легко восстановить НВП .
Общий вид алгоритма
9 | 9 | ||||
3 | 3 | ||||
3 | 10 | 10 | |||
3 | 4 | 4 | |||
3 | 4 | 8 | 8 | ||
1 | 4 | 8 | 1 | ||
1 | 2 | 8 | 2 | ||
1 | 2 | 8 | 12 | 12 | |
1 | 2 | 6 | 12 | 6 | |
1 | 2 | 5 | 12 | 5 | |
1 | 2 | 5 | 7 | 7 | |
1 | 2 | 5 | 7 | 11 | 11 |
predecessor | |||||||||||
---|---|---|---|---|---|---|---|---|---|---|---|
1 | 2 | 3 | 4 | 5 | 6 | 7 | 8 | 9 | 10 | 11 | 12 |
1 | 3 | 2 | 2 | 5 | 4 | 3 | 7 | 8 |
Псевдокод
function LIS([])[] B = PriorityQueue() k = 0 n = .size predecessor = [n] // резервируем позиций for i = 1 to n x = [i] B.insert(x) predecessor[x] = B.prev(x) if B.next(x) exists 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