Можно проще ...
Будем использовать только дихотомию, и для удобства вектора из с++
Теперь рассмотрим на примере
{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.