Если мы хотим восстановить саму подпоследовательность, то заведем массив предыдущих величин <tex>prev</tex> такой, что <tex>prev[i]</tex> - предпоследний элемент в НВП, оканчивающейся в элементе с номером <tex> i </tex>. Его значение будет изменяться вместе с изменением соответствующего i-ого элемента матрицы <tex>a</tex>.
<code>
lis = 0 int a[MaxN]; // maxN - наибольшая возможная длина НВПвозрастающей последовательности a = (n, 0) // заполняем нулямиint prev[maxN]; prev for i = (0 ... n, -1) // -1 - признак отсутствия предпоследнего элемента, что указывает на то, что данный элемент является первым в подпоследовательности a[1i] = 1 ; For prev[i ] = 2 to n-1; For for j = 1 to 0 ... i - 1 If (x[i] > x[j]) and if(a[j] + 1 > < a[i]) // нашли более оптимальную подпоследовательность a[i] = max(a[i], 1 + a[j]+1); prev[i] = j; int ans = d[0], pos = 0; lis for i = 0 ... n ans = max(lisans, ad[i]); pos = i; int it = 0; int lsa[maxN]; // наибольшая возрастающая последовательность <br> while(pos != -1) //восстанавливаем предка lsa[it] = pos; pos = prev[pos]; it = it + 1; for it - 1 ... 0 // вывод последовательности, начиная с первого элемента write(lsa[it])
</code>
Для вывода самой подпоследовательности достаточной пройти по массиву <tex>prev</tex>, начиная с номера того элемента, на котором мы зафиксировали наш ответ lis, и спускаясь по его предыдущим элементам, пока не достигнем -1 в предке очередного элемента.
