Контест Senior Задачи на Java обновлено
Длина наибольшей возрастающей подпоследовательности
Условие
Найдите длину самой длинной строго возрастающей подпоследовательности массива (элементы не обязаны идти подряд).
Ввод: в первой строке n (1 ≤ n ≤ 2·10⁴), во второй n чисел по модулю до 10⁹.
Вывод: одно число.
Пример
8
10 9 2 5 3 7 101 18
4
Как подойти
Patience sorting: массив хвостов + бинарный поиск.
Подсказки: 2
- Храните для каждой длины минимальный возможный «хвост».
- Массив хвостов отсортирован: ищите место бинарным поиском.
Решите в тренажёре
Редактор с автотестами прямо в браузере. Можно решить спокойно, вслух или под таймером, как на собесе.