НОП - наибольшая общая подпоследовательность. Даны две последовательности \(a\) и \(b\), возможно разной длины. Требуется найти подпоследовательность, входящую и в \(a\) и в \(b\), наибольшей длины. Решается простым динамическим программированием.
Пусть \(dp[i][j]\) - длина НОП на префиксах до \(i\) и \(j\), для \(a\) и \(b\) соответственно. Тогда переход будет очень простым: $$ dp[i][j] = max(dp[i][j-1], dp[i-1][j], dp[i-1][j-1] +eq) $$ Где \(eq\) равен \(1\), если \(a_i = b_j \), и нулю в противном случае. Асимптотика - \(O(n^2)\).
НВП - наибольшая возрастающая подпоследовательность. То есть из какого-то массива \(a\) длиной \(n\) мы выбираем набор индексов \(1 \le i_1 < i_2 < i_3 < ... i_k \le n\), и \(a_{i_1} < a_{i_2} ... < a_{i_k} \), причем \(k\) максимально.
Находить мы это можем двумя способами, а именно, двумя динамиками.
Давайте будем поддерживать \(d[i]\) - минимальное число, на которое заканчивается возрастающая подпоследовательность длины \(i\). Мы перебираем очередное \(a_j\), бинпоиском находим максимальное \(i\), такое что \(d[i] < a_j\), и обновляем \(d[i+1] = min(d[i+1],a_j)\). Важно понимать почему мы можем использовать бинпоиск: \(d\) - возрастает, так как подпоследовательности возрастающие, а значит и последний член тоже будет увеличиваться. Проинициализировать можно так: \(d[0] = - \infty; d[i] = + \infty, 1 \le i \le n\). Соответственно длина НВП будет равна максимальному \(i\), такому что \(d[i] \ne +\infty\)
Давайте тоже сделаем ДП, но такое, чтобы \(d[i]\) - длина НВП, заканчивающееся на \(i\). Чтобы обновить динамику на очередном \(a_j\), переберем все \(d[i], i < a_j\) и найдем по ним максимум. Прибавим один и присвоим это значение \(d[a_j]\). Это можно оптимизировать для асимптотики \(O(n \log{n})\) с помощью ДО или дерева Фенвика.
Второй вариант иногда полезней, так как можно считать всякие интересные штуки (кол-во НВП и т.п.).
Давайте решим простую задачу: найти НОП для \( a = \{ 1, 2, 3... n\} \) и \(p\), являющаяся перестановкой длины \(n\).
Легко заметить, что решением является НВП \(p\), так как все элементы \(a\) возрастают, соответственно НОП тоже возрастает.
Теперь решим задачу для двух разных перестановок. Достаточно представить первую перестановку в первом виде, а вторую закодировать на основе первой.
Рассмотрим на примере. Пусть дана перестановка \(a = \{ 5, 4, 3, 2, 1\}\) и \(p = \{ 5,1, 4,3,2\} \). Тогда представим \(a' = \{1,2, 3,4,5\} \). 5 будет соответствовать 1, 4 - 2, 3 - 3, 2 - 4 и 1 - 5. Таким образом, применем это правило к первой и второй перестановке. Тогда \(a' = \{1,2,3, 4,5\} \), а \(p' =\{1, 5, 2, 3, 4\}\). Ответ - НВП \(p\), который равен \(\{1,2,3,4\}\), и которому действительно соответствует НОП \(\{5,4,3,2\}\).
Таким образом, можно находить НОП двух перестановок за \(O(n \log{n}) \).
Более того, можно находить НОП любых двух массивов, где элементы не повторяются.
Пускай нужно найти НВП массива пар. Пара \((a,b)\) считается меньше пары \(c,d\) если \(a < c, b < d\). Тогда задача сводится к способу II подсчета НВП, только теперь нам нужна структура данных умеющая отвечать на запросы на плоскости, например двумерное ДО/двумерное дерево Фенвика и т.п. Асимптотика \(O(n \log^2{n})\).