Выбор ответа Senior Динамическое программирование обновлено
Наибольшая возрастающая подпоследовательность
Вопрос
Какую сложность даёт лучший известный подход к длине наибольшей возрастающей подпоследовательности?
Попробуйте сами
Выберите вариант, и откроется разбор.
Показать ответ и разбор
Коротко
Правильный ответ: O(n log n): массив хвостов и бинпоиск. Простое DP dp[i] = 1 + max(dp[j]) по j < i с a[j] < a[i] даёт O(n²).
Варианты ответа
- O(n log n): массив хвостов и бинпоискправильный ответ
- O(n): один проход с текущей длиной
- O(n²), и быстрее в общем случае нельзя
- O(2ⁿ): нужен перебор подпоследовательностей
Разбор
Простое DP dp[i] = 1 + max(dp[j]) по j < i с a[j] < a[i] даёт O(n²). Оптимизация: tails[k] минимальный хвост возрастающей подпоследовательности длины k + 1; для каждого элемента бинпоиском находим, куда его поставить. O(n log n).
- O(n) для этой задачи неизвестен в общем случае.
- O(n²) не предел.
- O(2ⁿ) это перебор подпоследовательностей.
Ответьте сами, а не прочитайте
В тренажёре вопрос попадёт в повторения и вернётся, когда начнёт забываться. Плюс билеты с зачётом: 20 вопросов, не больше 2 ошибок.