Контест Senior Задачи на Kotlin обновлено
Наибольшая возрастающая подпоследовательность за n log n
Условие
Найди длину наибольшей строго возрастающей подпоследовательности (элементы не обязаны идти подряд).
Ввод. n (1 ≤ n ≤ 7000), затем n чисел по модулю до 10^9.
Вывод. Длина подпоследовательности.
Сделай за O(n log n): квадратичную динамику на собесе попросят ускорить.
Как подойти
Подсказки: 2
- Храни минимальный «хвост» для каждой длины.
- Хвосты отсортированы: ищи позицию бинарным поиском.
Решите в тренажёре
Редактор с автотестами прямо в браузере. Можно решить спокойно, вслух или под таймером, как на собесе.