Изменения

Мы формируем новую стопку, когда встречаем элемент больший, чем вершины всех стопок, расположенных слева. В то же время стопки слева были созданы ранее, то есть элементы в них идут в исходной последовательности раньше текущего. Значит, появление новой стопки можно понимать как увеличение длины наибольшей возрастающей подпоследовательности на единицу (изначально длина НВП равна единице). Кроме того, каждая стопка представляет собой убывающую последовательность, т.е. длина НВП в пределах стопки равна единице. Поэтому длина наибольшей возрастающей подпоследовательности равна количеству стопок.

Для получения наибольшей возрастающей подпоследовательности при формировании стопок проведём следующие операции: каждый раз, положив элемент на вершину стопки, будем создавать указатель на возможный предыдущий элемент (вершину ближайшей слева стопки). В конце для получения наибольшей возрастающей подпоследовательности нужно выполнить <tex>p</tex> шагов, начав с вершины самой правой стопки: на <tex>i</tex>-м шаге записать в <tex>lis[0..p-1]</tex> на <tex>(p-i)</tex>-ю позицию текущий элемент, перейти к предыдущему элементу по указателю, <tex>p</tex> {{---}} количество стопок.