В данной последовательности надо найти наибольшую возрастающую подпоследовательность.
Я понял как это делать за время n*n. А как это можно сделать за n*log(n)

Расскажите пожалуиста

Частный случай задачи lis

или сразу сюда: Поиск. Строки и последовательности