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

Дан массив из [math]n[/math] чисел: [math]a[0..n - 1][/math]. Требуется найти в этой последовательности строго возрастающую подпоследовательность наибольшей длины.

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

Наибольшая возрастающая подпоследовательность (НВП) (англ. 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] - наибольшее из возможных.

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

Построим массив [math]d[/math], где [math]d[i][/math] [math]-[/math] это длина наибольшей возрастающей подпоследовательности, оканчивающейся в элементе, с индексом [math]i[/math]. Массив будем заполнять постепенно - сначала [math]d[0][/math], потом [math]d[1][/math] и т.д. Ответом на нашу задачу будет максимум из всех элементов массива [math]d[][/math]. Заполнение массива будет следующим: если [math]d[i] = 1[/math], то искомая последовательность состоит только из числа [math]a[i][/math]. Если [math]d[i] \gt 1[/math], то перед числом [math]a[i][/math] в подпоследовательности стоит какое-то другое число. Переберем его: это может быть любой элемент [math]a[j](j = 0...i - 1)[/math], но такой, что [math]a[j] \lt a[i][/math]. Пусть на каком-то шаге нам надо посчитать очередное [math]d[i][/math]. Все элементы массива [math]d[][/math] до него уже посчитаны. Значит наше [math]d[i][/math] мы можем посчитать следующим образом: [math]d[i] = max(d[j][/math], для всех [math]j = 0...i - 1)[/math] при условии, что [math]a[j] \lt a[i][/math].

Пока что мы нашли лишь максимальную длину наибольшей возрастающей подпоследовательности, но саму ее мы вывести не можем. Для восстановления ответа заведем массив [math]prev[0...n - 1][/math], где [math]prev[i][/math] будет означать индекс в массиве [math]a[][/math], при котором достигалось наибольшее значение [math]d[i][/math]. Для вывода ответа будем идти от элемента с максимальным значениям [math]d[i][/math] по его предкам.

vector<int> Find(vector<int> a)
    int n = a.size();//размер исходной последовательности
    vector<int> prev(n);
    vector<int> d(n);
    for i = 0...n - 1
        d[i] = 1;
        p[i] = -1;
        for j = 0...i - 1
            if a[j] < a[i]
                if d[j] + 1 > d[i]
                    d[i] = d[j] + 1;
                    prev[i] = j;
    int length = d[0], pos = 0;//length - длина наибольшей подпоследовательности, pos - последний символ наибольшей возрастающей подпоследовательности
    for i = 0...n - 1
        if d[i] > length
            length = d[i];
            pos = i;
    vector<int> answer;
    while pos != -1
        answer.push_back(a[pos]);
        pos = prev[pos];
    reverse(answer);
    return answer;    

Решение за 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].

vector <int> Find(vector <int> a)
{
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;
vector <int> answer;
while(it != -INF)
    answer.push_back(a[prev[it]]);
    it = a[prev[it]];
return answer;
}

Источники

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