Пример 4. Самый длинный возрастающий подмассив

Сегодня мы разберём ещё одну классическую задачу динамического программирования — поиск самого длинного возрастающего подмассива.

Постановка задачи

У нас есть массив чисел. Нужно найти длину самого длинного подмассива, в котором каждое следующее число строго больше предыдущего.

Пример:

array = [10, 2, 7, 15, 8, 22, 21, 3]

Возможные возрастающие подмассивы:

• [10, 7, 22]
• [7, 8]
• [10, 15, 22]
• [2, 7, 15, 22] ✅ (самый длинный, длина = 4)

Идея решения

Метод динамического программирования:

1. Создадим массив counts, где в позиции j будет храниться длина наибольшего возрастающего подмассива, который заканчивается на элементе array[j].
2. Изначально каждый элемент сам по себе образует подмассив длины 1.
3. Для каждого j будем проверять все предыдущие i (от 0 до j-1).

• Если array[j] > array[i], то можно «продлить» возрастающий подмассив на j.
• Тогда обновляем:

counts[j] = max(counts[j], counts[i] + 1)

Максимум среди counts и будет ответом.

Пример на Python

def LIS(array):
    n = len(array)
    counts = [1] * n  # каждый элемент сам по себе подмассив длины 1
    max_length = 1

    for j in range(1, n):
        for i in range(j):
            if array[j] > array[i]:
                counts[j] = max(counts[j], counts[i] + 1)
        max_length = max(max_length, counts[j])

    return max_length

# 🧪 Проверка
arr = [10, 2, 7, 15, 8, 22, 21, 3]
print("Длина самого длинного возрастающего подмассива:", LIS(arr))

Сложность

• Внешний цикл — n-1 раз
• Внутренний цикл — до j сравнений

Итого: O(n²).

Это не самое оптимальное решение, ведь задачу можно решить за O(n log n). Но зато такое решение интуитивное и отлично подходит для изучения динамики.