10
правок
Изменения
Нет описания правки
Для восстановления ответа будем поддерживать заполнение двух массивов:<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 n = a.size(); int d[maxN]length = 0; int posd[maxNn];//, pos[in] - позиция d[i] в a[i] int , prev[maxNn]; prev[0] = -1; d[0] = -INFINFINITY; for i = 01...n- 1 d[i] = INFINFINITY; for i = 0...n- 1 int j = binsearch(d[], a[i]);//поиск первого числа, строго большего 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]];//предок a[i] - позиция элемента d[j - 1] в исходном массиве a[i] size length = max(sizelength, j); int it = size; vector <int> answer; int pos = length; while(it pos != -INF)INFINITY answer.push_back(a[prev[itpos]]); it pos = a[prev[itpos]]; return answer; }
</code>
== Источники ==
