Longest Increasing Subsequence

Средняя№300одномерный массив

Дан массив чисел. Нужно выбрать часть из них, сохраняя порядок, так чтобы каждое выбранное число было больше предыдущего; стоять рядом им не обязательно. Сколько чисел можно выбрать самое большее? Наш пример: [4, 9, 5, 2, 6, 7, 3] — 4, например 4, 5, 6, 7.

300 Longest Increasing SubsequenceРазбор · 1×

Пример: [4, 9, 5, 2, 6, 7, 3]. Смотрите на 6 на индексе 4: она растёт от 5 за два места до неё, а не от соседней 2.

numslis041925324657631111111
i: это числозаполненоj: меньше, может стоять перед нимj: не меньше или не длиннееответ и его цепочка

lis[i]: самая длинная возрастающая цепочка, которая кончается на nums[i]. Каждое число само по себе — цепочка длины 1

01/29
сначала · назад · пуск · шаг
Скорость
1function lengthOfLIS(nums):
2 lis = array of size len(nums), all 1
3 for i from 1 to len(nums) - 1:
4 for j from 0 to i - 1:
5 if nums[j] < nums[i]:
6 lis[i] = max(lis[i], lis[j] + 1)
7 return max(lis)
состояние
lis
[1, 1, 1, 1, 1, 1, 1]
i
–
j
–
историянажмите шаг, чтобы вернуться

← → шаг · пробел — пауза

Почему это работает

  1. У любой возрастающей цепочки длиннее одного числа, которая кончается на nums[i], есть число прямо перед nums[i] — какое-то меньшее nums[j] с j < i. Отрежем nums[i], и останется цепочка, которая кончается на nums[j], длиной не больше lis[j]. Значит, lis[i] = 1 + наибольшее такое lis[j].
  2. Это j может стоять где угодно до i, поэтому проверяются все прежние числа, а не только сосед: для 6 стоящая прямо перед ней 2 даёт 2, а 5 за два места до неё — 3.
  3. Лучшая цепочка может кончаться где угодно, поэтому ответ — наибольшая клетка, а не последняя: здесь lis кончается на 2, а цепочка 4, 5, 6, 7 кончается на индексе 5.

Сложность

Время O(n²): каждое число один раз смотрит на все числа перед собой. Память O(n): по клетке на число. Есть способ быстрее, O(n log n): хранить наименьший конец цепочки каждой длины и искать место для числа двоичным поиском.

дальшеТеперь реши её сам, без подсказок.

Решить на LeetCode ↗

Задача и её условие принадлежат LeetCode. Здесь — наш пересказ, наш пример и наше решение. Patterns Hero не связан с LeetCode.