Задача о наибольшей возрастающей подпоследовательности
Дан массив из чисел: . Требуется найти в этой последовательности строго возрастающую подпоследовательность наибольшей длины.
| Определение: |
| Наибольшая возрастающая подпоследовательность (НВП) (англ. Longest increasing subsequence - LIS) строки длины - это последовательность символов строки таких, что , причем - наибольшее из возможных. |
Решение за время O(N2)
Построим массив , где это длина наибольшей возрастающей подпоследовательности, оканчивающейся в элементе, с индексом . Массив будем заполнять постепенно - сначала , потом и т.д. Ответом на нашу задачу будет максимум из всех элементов массива . Заполнение массива будет следующим: если , то искомая последовательность состоит только из числа . Если , то перед числом в подпоследовательности стоит какое-то другое число. Переберем его: это может быть любой элемент , но такой, что . Пусть на каком-то шаге нам надо посчитать очередное . Все элементы массива до него уже посчитаны. Значит наше мы можем посчитать следующим образом: , для всех при условии, что .
Пока что мы нашли лишь максимальную длину наибольшей возрастающей подпоследовательности, но саму ее мы вывести не можем. Для восстановления ответа заведем массив , где будет означать индекс в массиве , при котором достигалось наибольшее значение . Для вывода ответа будем идти от элемента с максимальным значениям по его предкам.
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)
Для более быстрого решения данной задачи построим следующую динамику: пусть - число, на которое оканчивается возрастающая последовательность длины , а если таких чисел несколько - то наименьшее из них. Изначально мы предполагаем, что , а все остальные элементы .
Заметим два важных свойства этой динамики: , для всех . А так же что каждый элемент обновляет максимум один элемент . Это означает, что при обработке очередного , мы можем за c помощью двоичного поиска в массиве найти первое число, которое строго больше текущего и обновить его.
Для восстановления ответа будем поддерживать заполнение двух массивов: и . В будем хранить позицию в , а в - позицию предыдущего элемента для .
vector<int> Find(vector<int> a)
int n = a.size();
int length = 0;
int d[n], pos[n], prev[n];
prev[0] = -1;
d[0] = -INFINITY;
for i = 1...n - 1
d[i] = INFINITY;
for i = 0...n - 1
int j = binsearch(d[], a[i]);
if d[j - 1] < a[i] and a[i] < d[j]
d[j] = a[i];
pos[j] = i;
prev[i] = pos[d[j - 1]];
length = max(length, j);
vector<int> answer;
int pos = length;
while pos != -INFINITY
answer.push_back(a[prev[pos]]);
pos = a[prev[pos]];
reverse(answer);
return answer;
