НВП

Пусть, дана последовательность из $n$ чисел $a_1,\ldots,a_n$. Требуется найти длину ее наибольшей возрастающей подпоследовательности (НВП), то есть длину такой наибольшей последовательности индексов $i_1<i_2<\ldots<i_k$, что $a[i_1]<a[i_2]<\ldots<a[i_k]$.

Пример: в последовательности $100, \underline{20}, \underline{75}, 0, -40, \underline{80}, -10, \underline{120}, 110$ наибольшей возрастающей подпоследовательность является $20, 75, 80, 120$: она имеет длину $4$. Возрастающих подпоследовательностей длины 5 здесь нет.

НВП за $O(N^2)$

Давайте решать наивно через динамическое программирование — то есть хранить в $dp[i]$ ровно то, что нам надо найти — длину НВП для первых $i$ чисел.

$dp[0] = 0$. Но как найти формулу, выражающую $dp[i]$ через предыдущие значения?

Ну, есть два варианта:

• $i$-ое число не входит в НВП. Тогда $dp[i] = 1$
• $i$-ое число входит в НВП. Тогда $dp[i] = 1 + dp[k]$, где $k$ — индекс предыдущего числа в этой НВП. Так давайте просто его переберем. При этом надо учесть, что $a[k]$ должно быть меньше, чем $a[i]$!* $i$-ое число входит в НВП. Тогда $dp[i] = 1 + dp[k]$, где $k$ — индекс предыдущего числа в этой НВП. Так давайте просто его переберем. При этом надо учесть, что $a[k]$ должно быть меньше, чем $a[i]$!исло входит в НВП. Тогда $dp[i] = 1 + dp[k]$, где $k$ — индекс предыдущего числа в этой НВП. Так давайте просто его переберем. При этом надо учесть, что $a[k]$ должно быть меньше, чем $a[i]$!

Итоговая формула получается такая:

$$dp[i] = \max(1, 1 + \max\limits_{k < i | a[k] < a[i]}dp[k])$$

Этот алгоритм работает за $O(N^2)$: у нас $O(N)$ состояний динамики, и каждое из них мы считаем за $O(N)$ действий, пока ищем этот максимум.

Ответ восстанавливается тем же способом: для каждого состояния нужно сохранить, где был этот максимум — там и есть предыдущее число в НВП.

НВП за $O(N\log{N})$

Решим эту задачу чуть более нестандартным динамическим программированием, где $min\_end[i]$ будет обозначать минимальное число, на которое может заканчиваться НВП длины $i$. При этом мы будем постепенно обрабатывать числа слева направо, и в этом массиве будет храниться только информация про все НВП в уже обработанном начале последовательности.

Изначально $min\_end[0]=-\infty, min\_end[i]=\infty$ для $i>0$. В качестве $\infty$ надо выбрать число, которое заведомо больше любого из $a_i$, аналогично с $-\infty$.

Рассматривая очередной элемент, попробуем продлить им каждую подпоследовательность:

Ответом будет максимальный такой индекс $j$, что $min\_end[j] \neq 0$. Это решение работает за $O(n^2)$.

Его можно значительно ускорить, заметив два факта: - На любом шаге $min\_end[i-1]\leq min\_end[i]$. Это легко доказать от противного. - Из предыдущего факта следует, что любое $a[i]$ обновит максимум одно значение динамики, так как попадет максимум в один интервал.

Значит, для поиска $j$, которое обновится, можно воспользоваться бинарным поиском. Это решение уже работает за $O(n\log n)$.

---

Автор конспекта: Глеб Лобанов

По всем вопросам пишите в telegram @glebodin