Задача о наибольшей возрастающей подпоследовательности

Определение:

Наибольшая возрастающая подпоследовательность (НВП) (англ. Longest increasing subsequence - LIS) строки [math] x [/math] длины [math] n [/math] - это последовательность [math] x[i_1] \lt x[i_2] \lt \dots \lt x[i_k] [/math] символов строки [math] x [/math] таких, что [math] i_1 \lt i_2 \lt \dots \lt i_k, 1 \le i_j \le n [/math], причем [math] k [/math] - наибольшее из возможных.

Задача заключается в том, чтобы отыскать это наибольшее [math] k [/math] и саму подпоследовательность. Известно несколько алгоритмов решения этой задачи.

Пример алгоритма, работающего за время [math] O(n^2) [/math]

Строим таблицу [math] a[1 \dots n] [/math]. Каждый её элемент [math] a[i] [/math] - длина наибольшей возрастающей подпоследовательности, оканчивающейся точно в позиции [math] i [/math]. Если мы построим эту таблицу, то ответ к задаче - наибольшее число из этой таблицы. Само построение тоже элементарно: [math] a[i] = \max{(a[j] + 1)} [/math],для всех [math] j = 1\dots i-1[/math], для которых [math] x[j] \lt x[i] [/math]. База динамики [math] a[1] = 1 [/math]. Если мы хотим восстановить саму подпоследовательность, то заведем массив предыдущих величин [math]prev[/math] такой, что [math]prev[i][/math] - предпоследний элемент в НВП, оканчивающейся в элементе с номером [math] i [/math]. Его значение будет изменяться вместе с изменением соответствующего i-ого элемента матрицы [math]a[/math].

lis = 0           // длина НВП
a = (n, 0)        // заполняем нулями
prev = (n, -1)    // -1 - признак отсутствия предпоследнего элемента, что указывает на то, что данный элемент является первым в подпоследовательности
a[1] = 1         
For i = 2 to n
  For j = 1 to i - 1
    If (x[i] > x[j]) and (a[j] + 1 > a[i]) // нашли более оптимальную подпоследовательность
      a[i] = a[j]+1
      prev[i] = j
    lis = max(lis, a[i])

Для вывода самой подпоследовательности достаточной пройти по массиву [math]prev[/math], начиная с номера того элемента, на котором мы зафиксировали наш ответ lis, и спускаясь по его предыдущим элементам, пока не достигнем -1 в предке очередного элемента.

Пример алгоритма, работающего за время [math] O(n\cdot\log n) [/math]

Для строки x будем по-прежнему хранить массивы [math]a[/math] ([math]a[/math] уже длины [math]n + 1[/math]) и [math]prev[/math], добавим к ним так же массив [math]last[/math] из [math]n + 1[/math] элементов так, что в [math]last[i][/math] хранится номер последнего элемента в возрастающей подпоследовательности длины [math]i[/math]. Теперь [math] a[i] [/math] содержит наименьший по величине элемент, на который может оканчиваться возрастающая подпоследовательность длины [math]i[/math], среди всех [math]x[j][/math], где [math]1 \leqslant j \leqslant i-1 [/math], если мы на шаге [math]i[/math]. В свою очередь, [math]prev[i][/math] хранит индекс предшевствующего символа для наибольшей возрастающей подпоследовательности, оканчивающейся в i-ой позиции. Заметим, что [math] a[0] \lt a[1] \lt a[2] \lt \dots \lt a[n] [/math]. Пусть мы находимся на i-ом шаге, тогда нам надо найти такой номер k [math] a[k] \leqslant x[i] \lt a[k+1] [/math] (если положить при начальной реализации [math] a[0] = -\inf[/math] - фиктивный элемент, [math]a[1] = a[2] = \dots = a[n] = \inf [/math], то такое k всегда найдется).Причем если в условии не строгое возрастание, то массив [math]a[/math] не убывает, и надо искать наибольшее k из возможных. После этого полагаем [math] a[k + 1] = x[i] [/math], а остальные элементы массива не меняем. В силу упорядоченности массива a, мы можем искать k бинарным поиском (при не строгом возрастании необходимо пользоваться функцией [math]upper_bound(1, n, a[i]))[/math], чтобы найти элемент [math]a[i][/math] с максимальным индексом. Параллельно нахождению НВП будем записывать массив предков [math]prev[/math] и номеров [math]last[/math]. Подсчитаем время: мы n раз выпоняем бинарный поиск, что требует [math] O(\log n) [/math] времени. Итого: [math] O(n\cdot\log n) [/math].

lis = 0
a = (n + 1, inf)
prev = (n, -1)
a[0] = -inf
last[0] = -1 
For i = 1 to n
   j = binary_search(0, n, x[i]) // бинарный поиск j < i, удовлетворяющего x[a[j]] < x[i] и x[i] < x[a[j + 1]]
   d[j + 1] = a[i]
   p[i] = last[j]
   last[j + 1] = i;
   If (lis < j + 1)
      lis = j + 1;

Для восстановления самой последовательности необходимой пройти по массиву pred с номера [math]last[lis][/math], выводя элементы НВП в обратном порядке, аналогично действиям в прошлом алгоритме.

Источники

• Наибольшая возрастающая подпоследовательность (НВП, Longest Increasing Subsequence, LIS)
• Длиннейшая возрастающая подпоследовательность за O (N log N)
• Задача поиска наибольшей увеличивающейся подпоследовательности