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

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

Наибольшая возрастающая подпоследовательность (НВП) (англ. 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]n[/math] чисел [math]a[0...n - 1][/math]. Требуется найти в этом массиве наибольшую возрастающую подпоследовательность.

Решение за время O(N²)

Строим таблицу [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].

int a[MaxN]; //maxN - наибольшая возможная длина возрастающей последовательности
int prev[maxN];
for i = 0 ... n
        a[i] = 1; 
        prev[i] = -1; 
        for j = 0 ... i - 1 
                if(a[j] < a[i])
                        a[i] = max(a[i], 1 + a[j]);
                        prev[i] = j; 
int ans = d[0], pos = 0; 
for i = 0 ... n 
        ans = max(ans, d[i]);
        pos = i;
int it = 0;
int lsa[maxN]; // наибольшая возрастающая последовательность 

while(pos != -1) //восстанавливаем предка
        lsa[it] = pos;
        pos = prev[pos];
        it = it + 1; 
for it - 1 ... 0 // вывод последовательности, начиная с первого элемента
        write(lsa[it])

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

Решение за O(NlogN)

Для более быстрого решения данной задачи построим следующую динамику: пусть [math]d[i](i = 0...n)[/math] - число, на которое оканчивается возрастающая последовательность длины [math]i[/math], а если таких чисел несколько - то наименьшее из них. Изначально мы предполагаем, что [math]d[0] = -[/math][math]\infty[/math], а все остальные элементы [math]d[i] =[/math] [math]\infty[/math]. Заметим два важных свойства этой динамики: [math]d[i - 1] \lt = d[i][/math], для всех [math]i = 1...n[/math]. А так же что каждый элемент [math]a[i][/math] обновляет максимум один элемент [math]d[j][/math]. Это означает, что при обработке очередного [math]a[i][/math], мы можем за [math] O(n\cdot\log n) [/math] c помощью двоичного поиска в массиве [math]d[][/math] найти первое число, которое строго больше текущего [math]a[i][/math] и обновить его. Для восстановления ответа будем поддерживать заполнение двух массивов:[math]pos[/math] и [math]prev[/math]. В [math]pos[i][/math] будем хранить позицию [math]d[i][/math] в [math]a[i][/math], а в [math]prev[i][/math] - позицию предыдущего элемента для [math]a[i][/math].

int d[maxN];
int pos[maxN];//pos[i] - позиция d[i] в a[i]
int prev[maxN];
prev[0] = -1;
d[0] = -INF;
for i = 0...n
    d[i] = INF;
for i = 0...n
    int j = binsearch(d, a[i]);//поиск первого числа, строго большего a[i]
    if(d[j - 1] < a[i] && a[i] < d[j])
         d[j] = a[i];
         pos[j] = i;
         prev[i] = pos[d[j - 1]];//предок a[i] - позиция элемента d[j - 1] в исходном массиве a[i]
         size = max(size, j);
int it = size;
int ans[size];
while(it != -INF)
    write(a[prev[it]]);//вывод наибольшей возрастающей последовательности в обратном порядке
    it = a[prev[it]];

Источники

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