Теоретический материал: наибольшая возрастающая подпоследовательность

Наибольшая возрастающая подпоследовательность (НВП, Longest Increasing Subsequence, LIS)

Условие

Дана последовательность a₁, …, a_n. Требуется найти ее возрастающую подпоследовательность наибольшей длины.

Решение

Первый способ

Сделаем копию данной последовательности и отсортируем ее по возрастанию. Тогда НВП будет также НВП для отсортированной последовательности. Поэтому достаточно найти наибольшую общую подпоследовательность исходной и отсортированной последовательности.

Обратите внимание: на самом деле таким способом мы найдем не возрастающую, а неубывающую подпоследовательность. Чтобы найти возрастающую подпоследовательность, нужно сделать еще один шаг (подумайте, какой!).

Сложность этого алгоритма – O(n²).

Второй способ

Попробуем воспользоваться методом динамического программирования. Пусть мы знаем НВП для последовательности a₁, …, a_k. Можем ли мы найти НВП для последовательности a₁, …, a_k+1? Кажется, что это легко сделать: если a_k+1 больше, чем последний член ранее найденной НВП, то a_k+1 нужно добавить в НВП, в противном случае нужно оставить НВП неизменной. К сожалению, такое решение оказывается неверным. Рассмотрим такой пример: 1 2 3 6 4 5. Для первых пяти членов этой последовательности длина НВП равна 4, но есть две различных НВП: 1 2 3 6 и 1 2 3 4. Пусть мы выбрали первую из них. Тогда на следующем шаге мы не сможем дополнить ее числом 5 и получим более короткую НВП (1 2 3 6) для всей последовательности, чем должны был получить (1 2 3 4 5).

Модифицируем предложенный алгоритм. Будем теперь запоминать не произвольную НВП, а ту, которая заканчивается на наименьшую возможную цифру. К сожалению, и этот способ не приведет нас к успеху. Рассмотрим такой пример: 1 4 2 3. Для последовательности из первых двух символов НВП будет иметь длину 2 (1 4). Но при добавлении символов длина НВП не увеличится, поскольку все оставшиеся числа меньше четырех.

Для решения задачи нам потребуется более сложная система подзадач. Пусть для последовательности a₁, a₂, …, a_k мы знаем возрастающие последовательности длины 1, 2, 3, ... Причем среди всех возрастающих последовательностей данной длины мы будем хранить ту, которая оканчивается на меньшее число. Тогда для последовательности a₁, a₂, …, a_k+1 мы сможем построить аналогичный набор последовательностей.

Опишем эту процедуру подробнее. Пусть LIS(k, s) – последний элемент возрастающей подпоследовательности длины s последовательности a₁, a₂, …, a_k.

Тогда следующий фрагмент программы полностью описывает динамические вычисления:

For k= 0 to n do
     for s= 1 to n do
           LIS(k, s) = plus infinity
 For k= 0 to n do
      LIS(k, 0) = minus infinity
 For k= 1 to n do
      for s= 1 to n do
           if ( LIS(k-1, s-1) < x(k) < LIS(k-1, s) 
                  then LIS(k,s)=x(k) 
                  else LIS(k,s)=LIS(k-1,s)

Третий способ

Мы будем постепенно строить возрастающие цепочки и в каждый момент времени для каждого элемента a_i хранить длину самой длинной построенной цепочки, заканчивающейся этим элементом.

Идею динамики лучше всего поясняет следующий код:

for i := 1 to n-1 do
  for j := i+1 to n do
    if a[j] > a[i] then
      if length[i] + 1 > length[j] then begin
        length[j] = length[i] + 1;
        predecessor[j] = i; //предшественник a[j] в цепочке
      end;

Изначально length[i]=1 для всех i, predecessor[i]=0.

Продемонстрируем работу алгоритма для последовательности 1,6,2,3,5.

До начала выполнения циклов:
  length: [1,1,1,1,1]
  predecessor: [0,0,0,0,0]

После выполнения цикла для i=1:
  length: [1,2,2,2,2], так как 6,2,3,5 > 1
  predecessor: [0,1,1,1,1]

После выполнения цикла для i=2:
  length: [1,2,2,2,2] – без изменений, так как 2,3,5 < 6
  predecessor: [0,1,1,1,1]

После выполнения цикла для i=3:
  length: [1,2,2,3,3], так как 3,5 > 2
  predecessor: [0,1,1,3,3]

После выполнения цикла для i=4:
  length: [1,2,2,3,4], так как 5 > 3
  predecessor: [0,1,1,3,4]

Таким образом, длина НВП равна 4, и всякая НВП заканчивается элементом 5, поскольку length[5]=4.

Используя массив predecessor, легко восстановить всю подпоследовательность:

Predecessor[5]=4, predecessor[4]=3, predecessor[3]=1, predecessor[1]=0.

Таким образом, НВП состоит из 1-го, 3-го, 4-го и 5-го элементов исходной последовательности: 1, 2, 3, 5.

Приведенный алгоритм имеет сложность O(n²).

Четвертый способ

Будем поочередно обрабатывать члены исходной последовательности. Пусть после обработки k-го элемента нам известно, что возрастающая подпоследовательность длины 1 может оканчиваться числом e[1], ВП длины 2 может оканчиваться числом e[2] и т.д., причем указанные числа e[i] – наименьшие возможные. Заметим, что е[1] < e[2] < e[3] <… Рассмотрим теперь число a_k+1. Найдем такое i, что e[i-1] ≤ a_k+1 < e[i] (если изначально положить e[0] = - ∞, а все остальные члены массива e равными +∞, то такое всегда найдется). Положим e[i]:= a_k+1, а остальные элементы массива e[i] оставим без изменений.

Заметим, что сложность поиска в упорядоченном массиве есть O(log m), где m – длина НВП, поэтому сложность приведенного алгоритма – О(n log m).