* Если <tex>\pi_i</tex> больше каждого элемента <tex>B</tex>, вычисленного для подпоследовательности <tex>\pi_1, \pi_2,~\dots~,\pi_{i-1}</tex>, тогда с ним можно сделать возрастающую подпоследовательность максимальной длины из уже рассмотренных, в которой он будет последним элементом. Значит, записываем его в конец <tex>B</tex>.
* Иначе <tex>\pi_i</tex> будет наилучшим элементом для уже существующей длиныи сможет улучшить только один элемент в <tex>B</tex>, тогда мы находим наименьшее <tex>k\colon B_k > \pi_i</tex> и заменяем <tex>B_k</tex> элементом <tex>\pi_i</tex>.
Следует отметить, что полученный массив также образует возрастающую последовательность, на котором мы должны выполнять операции <tex>\mathrm{insert}, \mathrm{next}, \mathrm{delete}</tex>, соответственно целесообразно использовать [[ Приоритетные очереди | приоритетную очередь]], реализованную через [[Дерево ван Эмде Боаса]]. Так как данная структура данных производит описанные операции за <tex>O(\operatorname{log} k)</tex>, где k — количество бит чисел, которые позволяет хранить дерево, то полученный алгоритм работает за <tex>O(n\operatorname{log}\operatorname{log} n)</tex>, потому что все элементы последовательности не превосходят n.
==== Доказательство оптимальности ====
{{
Утверждение
|id=proposal1
|statement=
Пусть <tex>S=\{\pi_1,\pi_2,~\dots,~\pi_n\}</tex> — входная перестановка. В результате описанного алгоритма размер массива <tex>B</tex> равен длине НВП последовательности <tex>S</tex>
|proof=
Докажем, что перед обработкой и после обработки элемента последовательности алгоритмом сохраняется инвариант, что в массиве <tex>B</tex> хранятся наилучшие элементы для каждой возможной длины возрастающих подпоследовательностей обработанной последовательности.
* Пусть перед обработкой элемента <tex>\pi_i</tex> соблюдается описанное выражение инварианта.
* Если <tex>\pi_i</tex> больше каждого элемента <tex>B</tex>, вычисленного для последовательности <tex>S_{i-1}=\{\pi_1,\pi_2,~\dots,~\pi_{i-1}\}</tex>, то он не может обновить любой из наилучших элементов, вычисленных ранее. С <tex>\pi_i</tex> можно составить возрастающую последовательность длины <tex>l+1</tex>, где <tex>l</tex> — длина НВП последовательности <tex>S_{i-1}</tex>, добавив <tex>\pi_i</tex> в конец этой НВП. Значит, <tex>\pi_i</tex> — наилучший элемент длины <tex>l+1</tex>. По предположению, размер <tex>B</tex> равен длине НВП последовательности <tex>S_{i-1}</tex>, потому что в <tex>B</tex> хранятся наилучшие элементы всех возможных длин возрастающих подпоследовательностей <tex>S_{i-1}</tex>. Тогда, добавив в конец очереди <tex>B</tex> элемент <tex>\pi_i</tex>, инвариант будет сохраняться.
* Иначе <tex>\pi_i</tex> будет наилучшим элементом для уже существующей длины. Заметим, что <tex>\pi_i</tex> может обновить только один элемент. Иначе, если <tex>\exists l_1,l_2\colon l_2>l_1</tex>, для которых <tex>\pi_i</tex> может быть наилучшим элементом, то существует такая подпоследовательность длины <tex>l_2</tex>, в которой <tex>\pi_i</tex> является наибольшим элементом, но из этой последовательности можно составить подпоследовательность длины <tex>l_1</tex>, в которой наибольший элемент меньше <tex>\pi_i</tex>, что противоречит предположению. Таким образом, <tex>\pi_i</tex> может обновить только наименьшее <tex>k\colon B_k > \pi_i</tex>. Тогда, заменив <tex>B_k</tex> элементом <tex>\pi_i</tex>, инвариант также будет сохраняться.
* После завершения алгоритма, в очереди <tex>B</tex> будут храниться наилучшие элементы для всех возможных длин возрастающих подпоследовательностей последовательности <tex>S</tex>. Тогда размер <tex>B</tex> равен длине НВП последовательности <tex>S</tex>.
}}
==== Пример ====
