Longest Increasing Subsequence
Дан список целых чисел nums. Подпоследовательность сохраняет некоторые элементы в исходном порядке, а остальные пропускает; сохранённые элементы не обязательно должны стоять рядом. Верните длину самой длинной подпоследовательности, значения которой строго возрастают слева направо. Два одинаковых значения подряд не считаются возрастанием.
Функция
- numsinteger-array
- список целых чисел, из которых нужно выбрать
- Возвращаетinteger
- длина наибольшей строго возрастающей подпоследовательности
Ограничения
1 ≤ nums.length ≤ 2500-104 ≤ nums[i] ≤ 104
Примеры
- Ввод
- nums = [3, 1, 8, 2, 5, 9, 4, 7]
- Вывод
- 4
- Пояснение
- 1, 2, 5, 9 возрастают, как и 1, 2, 5, 7 и 1, 2, 4, 7: длина 4. Ни один набор из пяти значений не сохраняет возрастание.
- Ввод
- nums = [7, 7, 7, 7]
- Вывод
- 1
- Пояснение
- Значения должны строго возрастать, поэтому никакие две семёрки не могут находиться в одной подпоследовательности. Один элемент сам по себе тоже считается подпоследовательностью, поэтому ответ — 1.
- Ввод
- nums = [12, -4, 0, 25, -10, 3, 16, 5]
- Вывод
- 4
- Пояснение
- -4, 0, 3, 16 имеет длину 4. Начиная с первого элемента, 12, можно получить только два значения, например 12, 25: лучшая подпоследовательность не обязана начинаться с начала.
Дополнительный вопрос
Можешь вернуть самую длинную возрастающую подпоследовательность вместе с её длиной и при этом уложиться во время O(n log n)?
Подсказки
Открывайте по одной. Каждая подсказывает чуть больше.
Лучшую подпоследовательность всего списка сложно описать напрямую. Зададим более узкий вопрос для каждого индекса
i: какова самая длинная возрастающая подпоследовательность, которая заканчивается именно наnums[i]?Подпоследовательность, заканчивающаяся на
nums[i], либо состоит только изnums[i], либо продолжает лучшую подпоследовательность, заканчивающуюся на некотором более раннемnums[j] < nums[i]. Выберите такойj, для которого значение наилучшее, и прибавьте единицу. Ответ — наибольшее из этих значений, независимо от того, на каком элементе оно заканчивается.Чтобы получить сложность ниже
O(n²), для каждой длины сохраняй только наименьшее значение, которым может заканчиваться подпоследовательность этой длины. Эти значения остаются отсортированными, поэтому с помощью бинарного поиска можно определить, удлиняет ли новое число самую длинную подпоследовательность или заменяет конечное значение.
Решение
Список из n чисел имеет 2^n подпоследовательностей — слишком много, чтобы проверить их все. Если для каждого индекса спрашивать, какова длина наилучшей возрастающей подпоследовательности, заканчивающейся именно там, получится таблица с временной сложностью O(n²). В самом быстром варианте для каждой длины хранится наименьшее значение, которым может заканчиваться подпоследовательность этой длины, а каждый элемент размещается с помощью бинарного поиска.
Взять или пропустить каждый элемент
Верно, но не успевает на самых больших тестах
Идея
Для каждого элемента реши, оставить его или нет; nums[i] можно оставить, только если он больше последнего оставленного значения. longest(i, prev) — это максимальное количество элементов, которое ещё можно добавить, начиная с индекса i, если последний оставленный элемент находится на позиции prev (или -1). Если пропустить элемент, получим longest(i+1, prev); если оставить — 1 + longest(i+1, i). Каждая возрастающая подпоследовательность соответствует одному пути выбора.
Для последовательности 1, 2, 3, ..., n оба варианта остаются возможными, а число вызовов удваивается с каждым элементом: 2^40 — это уже около 10^12. Однако существует не более n² различных пар (i, prev).
Алгоритм
- Напишите
longest(i, prev), гдеprev— индекс последнего сохранённого элемента или-1. - Если
iвыходит за конец, верните 0. - Пропустите
nums[i]:best = longest(i+1, prev). - Если
prevравен-1илиnums[i] > nums[prev], сохраните элемент:best = max(best, 1 + longest(i+1, i)). - Верните
best. Ответ —longest(0, -1).
def lengthOfLIS(nums):
def longest(i, prev):
# The longest increasing subsequence of nums[i:] whose values all exceed nums[prev].
# prev is -1 while nothing has been taken.
if i == len(nums):
return 0
best = longest(i + 1, prev) # skip nums[i]
if prev == -1 or nums[i] > nums[prev]:
best = max(best, 1 + longest(i + 1, i)) # take nums[i]
return best
return longest(0, -1)Наибольшая подпоследовательность, заканчивающаяся на каждом индексе
Идея
Пусть ending[i] — длина наибольшей возрастающей подпоследовательности, последним элементом которой является nums[i]. Если перед nums[i] есть элемент, то это некоторый nums[j], для которого j < i и nums[j] < nums[i], а подпоследовательность до него должна быть как можно длиннее. Значит, ending[i] = 1 + max(ending[j]) для таких j, а если их нет — 1. Заполняй таблицу слева направо.
Для [3, 1, 8, 2, 5, 9, 4, 7] таблица имеет вид [1, 1, 2, 2, 3, 4, 3, 4]: перед 5 могут идти 3, 1 или 2, и лучшая из этих подпоследовательностей имеет длину 2, поэтому ending[4] = 3. Ответ — наибольший элемент таблицы, поскольку лучшая подпоследовательность может заканчиваться где угодно.
n(n-1)/2 сравнений: примерно 3.1 × 10^6 для n = 2500.
Алгоритм
- Создай
ending, задав каждой записи значение 1. - Для каждого
iслева направо проверь всеj < i. - Если
nums[j] < nums[i], установи дляending[i]значениеending[j] + 1, если оно больше. - Верни наибольшее значение в
ending.
def lengthOfLIS(nums):
n = len(nums)
# ending[i]: the longest increasing subsequence that ends with nums[i]
ending = [1] * n
for i in range(1, n):
for j in range(i):
if nums[j] < nums[i] and ending[j] + 1 > ending[i]:
ending[i] = ending[j] + 1
return max(ending)Наименьшие хвосты с бинарным поиском
Идея
Для каждой длины оставляйте только наименьшее значение, которым может заканчиваться возрастающая подпоследовательность этой длины: tails[k] для длины k+1. Меньшее конечное значение никогда не хуже: всё, что может идти после 9, может идти и после 5. Значения в tails остаются строго возрастающими: если отбросить последнее значение возрастающей подпоследовательности длины k+2, получится подпоследовательность длины k+1, которая заканчивается меньшим значением.
Для каждого x выполните бинарный поиск первого значения в tails, которое ≥ x. Если такого значения нет, добавьте x: оно продолжает самую длинную подпоследовательность. Иначе замените это значение на x: подпоследовательность на единицу короче заканчивается числом меньше x, поэтому x даёт ту же длину с меньшим конечным значением.
Например, для примера 1 значения tails меняются так: [3], [1], [1, 8], [1, 2], [1, 2, 5], [1, 2, 5, 9], [1, 2, 4, 9], [1, 2, 4, 7]: длина равна 4. В последовательности [1, 2, 4, 9] число 4 встретилось после 9, поэтому смысл имеет только длина tails.
Алгоритм
- Начни с пустого списка
tails. - Для каждого
xвnumsвыполни двоичный поиск первого индексаk, для которогоtails[k] ≥ x. - Если нет элемента, который
≥ x, добавьxв конец списка. - Иначе установи
tails[k] = x. - Верни длину
tails.
from bisect import bisect_left
def lengthOfLIS(nums):
# tails[k]: the smallest last value of any increasing subsequence of length k + 1
tails = []
for x in nums:
k = bisect_left(tails, x) # the first tail that is >= x
if k == len(tails):
tails.append(x) # x extends the longest subsequence so far
else:
tails[k] = x # x is a smaller ending for length k + 1
return len(tails)
Ловушки и крайние случаи
- Возврат
ending[n-1]вместо наибольшего элемента. Для[1, 2, 3, 0]последний элемент равен 1, но ответ — 3. - Сравнение с
≤вместо<. Для[7, 7, 7, 7]нужно вернуть 1, а не 4. - В варианте с хвостами поиск первого хвоста
> xвместо≥ x. Тогда вторая 7 добавляется после первой, и равные значения считаются возрастающими. - По ошибке решается задача о непрерывной подпоследовательности. В примере 1 самая длинная возрастающая последовательность соседних элементов — 2, 5, 9 (длина 3), а ответ равен 4.
- Сохранение индексов с нуля в Lua или R, где массивы начинаются с 1. Маркер
prev = -1становится равным 0, а бинарный поиск выполняется по индексам от 1 до текущего размера.
Частые вопросы3
Какова временная сложность алгоритма поиска наибольшей возрастающей подпоследовательности?
Метод tails выполняется за время O(n log n) и использует O(n) памяти: один бинарный поиск для каждого элемента. Таблица по каждой паре индексов требует времени O(n²), а перебор всех подпоследовательностей — O(2ⁿ).
Что такое сортировка терпением в задаче о наибольшей возрастающей подпоследовательности?
Это метод tails, названный в честь карточной игры. Каждый «хвост» — это верхняя карта стопки: карта кладётся на самую левую стопку, верхняя карта которой не меньше её значения, или начинает новую стопку. Ответом будет количество стопок.
Как вместо этого найти самую длинную неубывающую подпоследовательность?
Разрешите равных соседей. В таблице используйте nums[j] ≤ nums[i]. В методе хвостов ищите первый хвост, строго больший, чем x, чтобы равное значение расширяло список, а не заменяло хвост. Тогда [7, 7, 7, 7] вернёт 4.
Похожие задачи
Задачи на те же идеи. Решите две или три, и приём запомнится.
def lengthOfLIS(nums):
# Напишите код здесьТест #1
Тест #2
Тест #3
Аргумент
nums = [3, 1, 8, 2, 5, 9, 4, 7]
Ожидаемый вывод
4