Изменения

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