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