Для каждой длины <tex>l = 1, 2,~\dots,~n</tex> предполагаемой НВП находим наименьший элемент, который может быть последним в возрастающей подпоследовательности длины <tex>l</tex> и запишем его в массив <tex>B_l</tex>. Будем называть его наилучшим элементом для длины <tex>l</tex>.
* Если <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>k\colon B_k > \pi_i</tex> и заменяем <tex>B_k</tex> элементом <tex>\pi_i</tex>.
* Если <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>k:\colon B_k > \pi_i</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.
==== Пример ====
