Самая длинная возрастающая подпоследовательность

Самая длинная возрастающая подпоследовательность (LIS)

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

Подход 1: Динамическое программирование O(n²)

Это наиболее интуитивное решение. Идея: для каждой позиции i вычислить длину LIS, заканчивающуюся в этом элементе.

Алгоритм:

• dp[i] = длина LIS, заканчивающаяся в элементе arr[i]
• Для каждого i проверяем все j < i
• Если arr[j] < arr[i], то можем продлить LIS из j

def lengthOfLIS(nums):
    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)

Сложность:

• Временная: O(n²) — два вложенных цикла
• Пространственная: O(n) — массив dp

Подход 2: Оптимальное решение с бинарным поиском O(n log n)

Это более сложное, но значительно более эффективное решение. Используется вспомогательный массив tails, где tails[i] — это наименьший конечный элемент LIS длины i+1.

Ключевая идея:

• Хотя мы не отслеживаем саму подпоследовательность, мы отслеживаем наименьшие возможные окончания для каждой длины
• Это позволяет использовать бинарный поиск для эффективного поиска позиции

import bisect

def lengthOfLIS_Optimal(nums):
    if not nums:
        return 0
    
    tails = []  # tails[i] = наименьший конец LIS длины i+1
    
    for num in nums:
        # Найдём позицию для вставки текущего числа
        pos = bisect.bisect_left(tails, num)
        
        if pos == len(tails):
            tails.append(num)
        else:
            tails[pos] = num
    
    return len(tails)

Сложность:

• Временная: O(n log n) — n итераций × log n на бинарный поиск
• Пространственная: O(n) — массив tails

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

Если нужна не только длина, но и сама подпоследовательность:

def lengthOfLIS_WithPath(nums):
    if not nums:
        return 0, []
    
    n = len(nums)
    dp = [1] * n
    parent = [-1] * n  # Для восстановления пути
    
    for i in range(1, n):
        for j in range(i):
            if nums[j] < nums[i] and dp[j] + 1 > dp[i]:
                dp[i] = dp[j] + 1
                parent[i] = j
    
    # Найдём индекс максимума
    max_length = max(dp)
    max_idx = dp.index(max_length)
    
    # Восстановим подпоследовательность
    lis = []
    idx = max_idx
    while idx != -1:
        lis.append(nums[idx])
        idx = parent[idx]
    
    return max_length, lis[::-1]

Пример использования

nums = [10, 9, 2, 5, 3, 7, 101, 18]

# Вариант 1: только длина
print(lengthOfLIS(nums))  # Выход: 4

# Вариант 2: оптимальный
print(lengthOfLIS_Optimal(nums))  # Выход: 4

# Вариант 3: длина и путь
length, path = lengthOfLIS_WithPath(nums)
print(length, path)  # Выход: 4 [2, 3, 7, 101]

Когда какой подход использовать

O(n²) подход:

• Когда n < 1000 (достаточно мал)
• Когда нужна максимальная читаемость
• Когда нужно восстановить саму подпоследовательность

O(n log n) подход:

• Когда n очень большое (> 10⁵)
• Когда нужна максимальная производительность
• Когда работаешь с потоками данных в real-time

Практические применения

• Анализ трендов в финансовых данных
• Алгоритмы сжатия и версионирования
• Предсказание паттернов в пользовательском поведении
• Обработка временных рядов в data science
• Задачи с препятствиями (LIS с доп. условиями)

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

❌ Путаница со strict и non-strict возрастанием

❌ Неправильное использование бинарного поиска (bisect_left vs bisect_right)

❌ Забывают инициализировать dp[i] = 1