Наибольшая возрастающая подпоследовательность
DP за O(n^2), а затем приём за O(n log n)
«Наибольшая возрастающая подпоследовательность» — бесплатный урок Coding Interview Prep на CoddyKit. Это урок 4 из 4. Ты можешь прочитать весь урок бесплатно ниже — а потом практиковать его прямо в браузере с встроенным редактором кода и ИИ-репетитором 24/7. Это часть пути обучения Coding Interview Prep, и твой прогресс синхронизируется между веб-версией и приложением CoddyKit. Курс Coding Interview Prep содержит 4 уроков всего.
Что такое LIS
Подпоследовательность сохраняет порядок элементов, но может пропускать некоторые из них. Наибольшая возрастающая подпоследовательность — это самая длинная такая последовательность, которая строго возрастает.
a = [3, 1, 4, 1, 5, 9, 2]Подпоследовательность, а не подмассив
В отличие от подмассива, LIS не обязана быть непрерывной. Можно перескакивать через меньшие числа, чтобы продолжить цепочку.
Состояние DP за O(n^2)
Пусть dp[i] — длина LIS, которая заканчивается в позиции i. Каждый элемент сам по себе образует подпоследовательность длины не меньше единицы.
dp = [1] * nПереход за O(n^2)
Для каждого i рассмотрите все предыдущие j. Если a[j] меньше, расширьте последовательность: dp[i] = max(dp[i], dp[j] + 1).
for i in range(n):
for j in range(i):
if a[j] < a[i]:
dp[i] = max(dp[i], dp[j]+1)Прочитайте ответ
Результат — наибольшее значение в таблице, поскольку LIS может заканчиваться где угодно, а не только в последней позиции.
answer = max(dp)Почему O(n^2) может привести к TLE
Двойной цикл работает за O(n в квадрате). При n около 100000 это слишком медленно и приводит к вердикту о превышении лимита времени.
Идея метода терпеливой сортировки
Быстрый метод хранит список из наименьших возможных конечных элементов для каждой длины подпоследовательности — по аналогии с терпеливой сортировкой.
tails = []Размещайте с помощью двоичного поиска
Для каждого числа двоичным поиском найдите подходящую позицию среди конечных элементов с помощью bisect_left, получив общую сложность O(n log n).
from bisect import bisect_leftРасширяйте или заменяйте
Если позиция находится за концом списка, используйте append, чтобы увеличить LIS. Иначе замените конечный элемент на это меньшее значение.
i = bisect_left(tails, x)
if i == len(tails):
tails.append(x)
else:
tails[i] = xДлина хранится в tails
Когда просмотр завершён, len(tails) — это длина LIS. Сам список не всегда является подпоследовательностью, но его длина всегда точна.
answer = len(tails)Строго возрастающая и неубывающая последовательности
Для неубывающего варианта переключитесь на bisect_right, чтобы одинаковые значения могли продолжать цепочку.
from bisect import bisect_rightБыстрая проверка
Какой метод находит длину LIS за O(n log n)?
Итоги: от n^2 к n log n
Теперь Вы умеете решать задачу о LIS двумя способами. DP за O(n^2) прост, а метод конечных элементов с двоичным поиском подходит для больших входных данных и укладывается в лимит времени.
Часто задаваемые вопросы
Урок «Наибольшая возрастающая подпоследовательность» бесплатный?
Да — полный текст урока «Наибольшая возрастающая подпоследовательность» бесплатно доступен здесь в веб-версии. Чтобы практиковать его интерактивно (встроенный редактор кода и ИИ-репетитор 24/7) и разблокировать остальной курс Coding Interview Prep, подпишись на CoddyKit PRO. Курс Coding Interview Prep содержит 4 уроков всего.
Чему я научусь в уроке «Наибольшая возрастающая подпоследовательность»?
DP за O(n^2), а затем приём за O(n log n) Ты практикуешь Coding Interview Prep с помощью реального кода, который запускаешь прямо в браузере, и ИИ-репетитор 24/7 отвечает на твои вопросы во время урока.
Нужен ли мне опыт, чтобы начать Coding Interview Prep?
Предыдущий опыт не требуется. Coding Interview Prep на CoddyKit структурирован для всех уровней — от новичков до продвинутых, поэтому ты можешь начать отсюда или с самого начала и учиться в своем темпе. Это урок 4 из 4.
Сколько времени занимает урок «Наибольшая возрастающая подпоследовательность»?
Большинство уроков CoddyKit занимают около 5–10 минут. Каждый из них компактный и интерактивный, поэтому ты постоянно делаешь прогресс и продолжаешь с того же места в веб-версии и приложении.
Можно ли писать и запускать код в этом уроке Coding Interview Prep?
Да. Каждый урок Coding Interview Prep включает встроенный редактор кода, поэтому ты пишешь и запускаешь реальный код прямо в браузере и получаешь моментальную обратную связь от AI — локальная установка не требуется.
Все уроки этого курса
- Мемоизация и табуляция
- Определение состояния и перехода
- Лестница и сочетания монет
- Наибольшая возрастающая подпоследовательность