10
правок
Изменения
Нет описания правки
Дан массив из <tex>n</tex> чисел: <tex>a[0..n]</tex>. Требуется найти в этой последовательности строго возрастающую подпоследовательность наибольшей длины.
{{Определение
|definition =
'''Наибольшая возрастающая подпоследовательность (НВП)''' (''англ''. Longest increasing subsequence - LIS) строки <tex> x </tex> длины <tex> n </tex> - это последовательность <tex> x[i_1] < x[i_2] < \dots < x[i_k] </tex> символов строки <tex> x </tex> таких, что <tex> i_1 < i_2 < \dots < i_k, 1 \le i_j \le n </tex>, причем <tex> k </tex> - наибольшее из возможных.
}}
Если мы хотим восстановить саму подпоследовательность, то заведем массив предыдущих величин <tex>prev</tex> такой, что <tex>prev[i]</tex> - предпоследний элемент в НВП, оканчивающейся в элементе с номером <tex> i </tex>. Его значение будет изменяться вместе с изменением соответствующего i-ого элемента матрицы <tex>a</tex>.
===Псевдокод===
<code>
vector <int > Find(vector <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;
vector <int it = 0; int lsa[maxN]> answer; // наибольшая возрастающая последовательность <br>
while(pos != -1) //восстанавливаем предка
pos = prev[pos];
</code>
Для более быстрого решения данной задачи построим следующую динамику: пусть <tex>d[i](i = 0...n)</tex> - число, на которое оканчивается возрастающая последовательность длины <tex>i</tex>, а если таких чисел несколько - то наименьшее из них. Изначально мы предполагаем, что <tex>d[0] = -</tex><tex>\infty</tex>, а все остальные элементы <tex>d[i] =</tex> <tex>\infty</tex>.
Заметим два важных свойства этой динамики: <tex>d[i - 1] <= d[i]</tex>, для всех <tex>i = 1...n</tex>. А так же что каждый элемент <tex>a[i]</tex> обновляет максимум один элемент <tex>d[j]</tex>. Это означает, что при обработке очередного <tex>a[i]</tex>, мы можем за <tex> O(n\cdot\log n) </tex> c помощью двоичного поиска в массиве <tex>d[]</tex> найти первое число, которое строго больше текущего <tex>a[i]</tex> и обновить его.
Для восстановления ответа будем поддерживать заполнение двух массивов:<tex>pos</tex> и <tex>prev</tex>. В <tex>pos[i]</tex> будем хранить позицию <tex>d[i]</tex> в <tex>a[i]</tex>, а в <tex>prev[i]</tex> - позицию предыдущего элемента для <tex>a[i]</tex>.
===Псевдокод===
<code>
vector <int> Find(vector <int> a)
{
int d[maxN];
int pos[maxN];//pos[i] - позиция d[i] в a[i]
size = max(size, j);
int it = size;
vector <int ans[size]> answer;
while(it != -INF)
it = a[prev[it]];
return answer;
}
</code>
== Источники ==
