57
правок
Изменения
→Алгоритм
Имеем массив <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</tex> — количество стопок, на <tex>p-i</tex>-ю позицию текущий элемент, перейти к предыдущему элементу по указателю, <tex>p</tex> — количество стопок.
== Сложность ==
