Задача о поиске НВП

Дана последовательность $a$ из $n$ элементов. Необходимо найти в ней наибольшую по длине возрастающую подпоследовательность.

Рассмотрим пример.

Пусть $a = [1, 3, 2, 5, 4]$. Тут несколько НВП максимальной длины:

• $1, 2, 4$
• $1, 3, 5$

Легко увидеть, что искомой подпоследовательности длины 4 для этого массива $a$ нет.

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

Воспользуемся методом динамического программирования на префиксе и решим задачу по стандартному плану:

• Сформулировать, что будет хранить каждое состояние.

  $dp[i]$ - максимальная длина НВП, которая заканчивается в элементе $a[i]$.

• Найти формулу перехода.

  Есть два варианта:

  1. $dp[i] = 1$, то есть НВП состоит только из $a[i]$
  2. Есть такой $j$ от 0 до $i - 1$, что a[j] < a[i]. Тогда в НВП, соответсвующую $dp[j]$, можно добавить в конец $a[i]$. Заметим, что таких $j$ может быть несколько, поэтому нужно выбрать максимум.

  Получим финальную формулу:

  \[dp[i] = 1 + \max_{^{\forall j = 0 \ldots i - 1}_{a[j] < a[i]}} dp[j]\]

  Для удобства будем считать, что $\max \emptyset = 0$

• Задать значения базы динамики.

  $dp[0] = 1$

• Понять, где лежит ответ.

  $\max dp[i]$

Асимптотика получается $O(n^2)$, ведь $dp[i]$ мы пересчитываем за линейный поиск максимума.

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

Чтобы решить задачу эффективнее, немного поменяем состояние динамики.

• Сформулировать, что будет хранить каждое состояние.

  $dp[i]$ - это число, на которое заканчивается НВП длины $i$. Если таких чисел несколько, то берем минимальное из них.

• Задать значения базы динамики.

  $dp[0] = -\infty$

  $dp[1\ldots] = \infty$

• Найти формулу перехода.

  Формулы перехода в явном виде тут нет.

  Однако значения динамики можно обновлять, последовательно рассматривая числа $a[i]$.

  for (int i = 0; i < n; i++)
        for (int j = 1; j <= n; j++)
          if (dp[j - 1] < a[i] && a[i] < dp[j])
                dp[j] = a[i];
  

  Чтобы понять, как быстро пересчитывать такую динамику, нужно заметить несколько ее хороших свойств:

  1. $dp[i - 1] <= dp[i]$
  2. $a[i]$ обновит не больше одно значения из $dp$

  Это значит, что мы можем бинпоиском искать для $a[i]$ место в $dp$, которое оно обновит.

  for (int i = 0; i < n; i++) {
         int j = upper_bound(d.begin(), d.end(), a[i]) - d.begin();
         if (dp[j - 1] < a[i] && a[i] < dp[j])
               dp[j] = a[i];
  }
  

• Понять, где лежит ответ.

  \[\max_{dp[i] \neq \infty} i\]

НОП

Даны две последовательности $a$ и $b$. Требуется узнать длину их наибольшей общей подпоследовательности.

Пусть $n$ - длина $a$, а $m$ - длина $b$.

Решим задачу методом динамического программирования:

• Сформулировать, что будет хранить каждое состояние.

  Мы будем хранить $dp[i][j]$ - длину НОП, если мы рассматриваем префикс длины $i$ у $a$ и $j$ у $b$.

• Найти формулу перехода.

  Если $a[i - 1] = b[j - 1]$, то НОП точно их содержит и $dp[i][j] = dp[i - 1][j - 1] + 1$.

  Кроме того, мы всегда можем получить $dp[i][j] = max(dp[i - 1][j], dp[i][j - 1])$.

  Таким образом итоговая формула выглядит так:

  if a[i - 1] == b[j - 1]:
      dp[i][j] = dp[i - 1][j - 1] + 1
  else:
      dp[i][j] = max(dp[i - 1][j], dp[i][j - 1])
  

• Задать значения базы динамики.

  $dp[i][0] = 0, dp[0][j] = 0$ для всех $i, j$.

• Понять, где лежит ответ.

  $dp[n][m]$

  Мы создаем массив размера $nm$, после чего проходимся по каждому его элементу и пересчитываем его за $O(1)$, значит, итоговая сложность - $O(nm)$.