Задача о наибольшей возрастающей подпоследовательности
Дан массив из чисел: . Требуется найти в этой последовательности строго возрастающую подпоследовательность наибольшей длины.
| Определение: |
| Наибольшая возрастающая подпоследовательность (НВП) (англ. 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 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;
}
