10
правок
Изменения
Нет описания правки
__TOC__Дан массив из <tex>n</tex> чисел: <tex>a[0..n- 1]</tex>. Требуется найти в этой последовательности строго возрастающую подпоследовательность наибольшей длины.
{{Определение
|definition =
}}
== Решение за время O(N<sup>2</sup>) ==
<code>
vector <int> Find(vector <int> a) { int n = a.size();//размер исходной последовательности vector<int > prev[maxN](n); vector<int> d(n);//массив предков for i = 0...n- 1 ad[i] = 1; prevp[i] = -1; for j = 0...i - 1 if(a[j] < a[i]) a if d[j] + 1 > d[i] = max(a d[i], 1 + a= d[j])+ 1; prev[i] = j; int ans length = d[0], pos = 0; //length - длина наибольшей подпоследовательности, pos - последний символ наибольшей возрастающей подпоследовательности for i = 0...n - 1 ans if d[i] > length length = max(ans, d[i]); pos = i; vector <int> answer; while(pos != -1) //восстанавливаем предка answer.push_back(a[pos]);
pos = prev[pos];
</code>
== Решение за O(NlogN) ==
Для более быстрого решения данной задачи построим следующую динамику: пусть <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)
