Наибольшая возрастающая подпоследовательность: O(n²) и O(n log n)

Коротко

Задача

Дан массив чисел. Нужно найти самую длинную подпоследовательность, элементы которой строго возрастают.

[10, 9, 2, 5, 3, 7, 101, 18]
      →  [2, 3, 7, 101]  длина 4
      или [2, 3, 7, 18]  тоже 4

Важно: подпоследовательность, а не подмассив. Элементы не обязаны идти подряд, но порядок сохраняется.

Задача встречается сама по себе и как часть более сложных: планирование задач, укладка коробок, поиск возрастающих трендов, задача о разбиении на цепочки.

Решение за O(n²)

Естественная формулировка динамики.

dp[i] — длина наибольшей возрастающей подпоследовательности, которая заканчивается элементом i.

Переход: смотрим на все предыдущие элементы. Если какой-то из них меньше текущего, к его подпоследовательности можно приписать текущий элемент.

dp[i] = 1 + max(dp[j])  для всех j < i, где nums[j] < nums[i]

Если подходящих j нет, dp[i] = 1 — элемент сам по себе.

def lis_quadratic(nums: list[int]) -> int:
    if not nums:
        return 0

    n = len(nums)
    dp = [1] * n           # каждый элемент — подпоследовательность длины 1

    for i in range(1, n):
        for j in range(i):
            if nums[j] < nums[i]:
                dp[i] = max(dp[i], dp[j] + 1)

    return max(dp)


print(lis_quadratic([10, 9, 2, 5, 3, 7, 101, 18]))   # 4

Разберём таблицу:

nums: 10  9  2  5  3  7  101  18
dp:    1  1  1  2  2  3   4    4
                              ↑ ответ = 4

Ответ — максимум по всему массиву dp, а не последний элемент. Наибольшая подпоследовательность не обязана заканчиваться последним числом. Это самая частая ошибка в этой задаче.

Решение за O(n log n)

Квадрат не проходит при n = 10⁵. Есть более хитрый подход.

Будем поддерживать массив tails, где tails[k] — наименьший возможный последний элемент возрастающей подпоследовательности длины k+1.

Ключевое наблюдение: этот массив всегда отсортирован. Значит нужную позицию можно искать бинарным поиском.

Для каждого числа:

• если оно больше всех в tails — приписываем в конец, длина выросла;
• иначе находим первый элемент, который не меньше текущего, и заменяем его.

import bisect


def lis_fast(nums: list[int]) -> int:
    tails = []

    for num in nums:
        pos = bisect.bisect_left(tails, num)

        if pos == len(tails):
            tails.append(num)        # новая максимальная длина
        else:
            tails[pos] = num         # улучшили окончание длины pos+1

    return len(tails)


print(lis_fast([10, 9, 2, 5, 3, 7, 101, 18]))   # 4

Как это работает

Проследим на примере:

num=10:  tails = [10]
num=9:   9 < 10 → заменяем        tails = [9]
num=2:   2 < 9  → заменяем        tails = [2]
num=5:   больше всех → добавляем  tails = [2, 5]
num=3:   3 < 5  → заменяем        tails = [2, 3]
num=7:   больше всех → добавляем  tails = [2, 3, 7]
num=101: больше всех → добавляем  tails = [2, 3, 7, 101]
num=18:  18 < 101 → заменяем      tails = [2, 3, 7, 18]

длина = 4

Важнейшая оговорка: массив tails — это не сама подпоследовательность. В примере выше [2, 3, 7, 18] случайно оказалась корректной, но так бывает не всегда. tails хранит лишь наилучшие окончания для каждой длины, и его содержимое может быть невалидной последовательностью.

Замена элемента улучшает будущие возможности: чем меньше последний элемент подпоследовательности данной длины, тем больше чисел можно к ней приписать потом.

Восстановление самой подпоследовательности

Для быстрой версии нужен дополнительный массив предшественников.

import bisect


def lis_with_sequence(nums: list[int]) -> list[int]:
    if not nums:
        return []

    tails = []            # значения окончаний
    tails_idx = []        # индексы этих окончаний в nums
    prev = [-1] * len(nums)

    for i, num in enumerate(nums):
        pos = bisect.bisect_left(tails, num)

        if pos > 0:
            prev[i] = tails_idx[pos - 1]     # предыдущий элемент цепочки

        if pos == len(tails):
            tails.append(num)
            tails_idx.append(i)
        else:
            tails[pos] = num
            tails_idx[pos] = i

    # разматываем цепочку с конца
    result = []
    k = tails_idx[-1]
    while k != -1:
        result.append(nums[k])
        k = prev[k]

    return result[::-1]


print(lis_with_sequence([10, 9, 2, 5, 3, 7, 101, 18]))
# [2, 3, 7, 18]
print(lis_with_sequence([0, 1, 0, 3, 2, 3]))
# [0, 1, 2, 3]

Массив prev запоминает, откуда пришли, и позволяет восстановить настоящую подпоследовательность, а не содержимое tails.

Строгое и нестрогое возрастание

Разница в одной функции.

bisect.bisect_left(tails, num)    # строго возрастающая: 1 < 2 < 3
bisect.bisect_right(tails, num)   # неубывающая: 1 ≤ 2 ≤ 2 ≤ 3

bisect_left находит первый элемент не меньше num и заменяет его — равные значения вытесняются, поэтому последовательность строго возрастает.

bisect_right находит первый элемент строго больше — равные значения сохраняются, и получается неубывающая последовательность.

Условие задачи нужно читать внимательно: «возрастающая» обычно означает строго, «неубывающая» — нестрого.

Связанные задачи

Наибольшая убывающая — разверните массив или поменяйте знак сравнения.

Наименьшее число неубывающих подпоследовательностей, на которые разбивается массив, равно длине наибольшей строго убывающей (теорема Дилворта).

Задача о вложенных конвертах. Отсортировать по ширине, потом найти НВП по высоте. Тонкость: при равной ширине сортировать высоту по убыванию, чтобы конверты одной ширины не образовали цепочку.

def max_envelopes(envelopes: list[tuple]) -> int:
    # ширина по возрастанию, при равной — высота по убыванию
    envelopes.sort(key=lambda e: (e[0], -e[1]))
    return lis_fast([h for _, h in envelopes])


print(max_envelopes([(5, 4), (6, 4), (6, 7), (2, 3)]))   # 3

Задача о лестнице из коробок, о расстановке зданий, о максимальном числе непересекающихся отрезков — все сводятся к НВП.

Частые ошибки

Возврат dp[n-1] вместо максимума. В квадратичной версии — самая частая ошибка.

Использование tails как ответа. Массив не является подпоследовательностью; для ответа нужен prev.

Путаница bisect_left и bisect_right. Даёт неверный ответ на массивах с повторами, а на массивах без повторов работает — поэтому баг легко пропустить.

Забытый пустой массив. max() на пустом dp упадёт.

Что запомнить

• НВП ищет подпоследовательность (элементы не обязаны идти подряд), а не подмассив.
• Динамика за O(n²): dp[i] — длина НВП, заканчивающейся в i; ответ это максимум по всему dp.
• Быстрая версия за O(n log n) хранит наименьшие окончания подпоследовательностей каждой длины.
• Массив tails не является ответом — для восстановления нужен массив предшественников.
• bisect_left даёт строгое возрастание, bisect_right — нестрогое.

Пройди собеседование в топ-компанию

Платформа для подготовки

Решай алгоритмические задачи как профи

✓ Популярные алгоритмы✓ Разбор решений✓ AI помощь

Начать сейчас→