Контест Middle Динамическое программирование спрашивают часто обновлено
Наибольшая возрастающая подпоследовательность за n log n
Условие
Дан массив из n чисел. Найдите длину наибольшей строго возрастающей подпоследовательности (элементы идут в исходном порядке, но не обязательно подряд).
Ввод: в первой строке n (1 ≤ n ≤ 2500), во второй n чисел (|aᵢ| ≤ 10⁹).
Вывод: длина подпоследовательности.
Пример 1
Ввод:
8
10 9 2 5 3 7 101 18
Вывод:
4
Пример 2
Ввод:
3
2 2 2
Вывод:
1
Как подойти
Подсказки: 2
- Храните для каждой длины наименьший возможный хвост.
- Массив хвостов отсортирован: ищите место бинарным поиском.
Решите в тренажёре
Редактор с автотестами прямо в браузере. Можно решить спокойно, вслух или под таймером, как на собесе.
Предыдущий вопрос
Рюкзак 0/1: максимальная ценность
Следующий вопрос
Подъём по лестнице с минимальной платой