Разбиение перестановки на подпоследовательности

Пусть дана перестановка чисел 1..N. Построим граф с N вершинами и в худшем случае с O(N^2) ребрами таким образом:
* Вершинами будут элементы перестановки.
* Ребро между вершинами i и j есть тогда и только тогда, тогда i<j и a_i<a_j.

Найдем минимальное покрытие путями этого графа. Очевидно, что оно и будет минимальным покрытием искомой перестановки возрастающими подпоследовательностями.

Сложность алгоритма O(N^5/2).

Как оказалось, жадность тут работает правильно. Можно просто брать первый элемент, искать первый который больше его и идет после него, затем для него повторять то же самое и т.д.. После этого всю последовательность вычеркиваем и повторяем то же самое с начала. При помощи простого дерева отрезков это можно за O(NlogN) реализовать.

Можно проще ...
Будем использовать только дихотомию, и для удобства вектора из с++
Теперь рассмотрим на примере
{1, 7, 4, 6, 9, 3, 2, 8, 5, 10}
Пусть нам поступила 1.
Запишем её {1}.
Далее поступает 7, запишем её после 1. Получим {1, 7}
Далее идёт 4, запишем её в новую строку, получим
{1, 7}
{4}
далее 6, запишем после 4, получим.
{1, 7}
{4, 6}
далее 9, запишем после 7, получим
{1, 7, 9}
{4, 6}
И так далее, на каждом ходу ищем из существующих строк, как можно высшию, что бы последнее число не превышало добавляемого числа, если таких строк нет, то добавляем в новую строку. ...
далее буду получатся вот такие ходы:
{1, 7, 9}
{4, 6}
{3}
....
{1, 7, 9}
{4, 6}
{3}
{2}
....
{1, 7, 9}
{4, 6, 8}
{3}
{2}
.....
{1, 7, 9}
{4, 6, 8}
{3, 5}
{2}
....
{1, 7, 9, 10}
{4, 6, 8}
{3, 5}
{2}

В итоге получаем 4 покрывающих последовательности!
Ищем мы строку обычной дихотомией! Теперь почему этот жадный правилен.
Если нам надо поставить число X, и его на текущий момент допустим можно поставить в конец како-то последовательности,или начать с него новую последовательность.
Тогда, нам всегда выгодно поставить в конец, чем создавать новое ... Так же в случае когда нужно выбирать между строками, то нужно выбирать с максимально близким меньшим к нему числом! Это всё несложно увидеть посмотрев на различные последовательности...

И того можно написать так, прямо при чтении для каждого числа ищем дихотомией его местоположение, и пихаем его в конец найденной строки.

NlogN.