Алгоритм поиска максимальной подпоследовательности

Поиск максимальной подпоследовательности – классическая задача оптимизации над массивами, в которой требуется найти подпоследовательность, максимизирующую заданный функционал. В базовой постановке – максимальная сумма непрерывной подпоследовательности (задача Кадане). Часто встречаются и вариации: максимальная возрастающая подпоследовательность (LIS), максимальная сумма с ограничениями (по длине, по модулю, по чётности), а также версии с непрерывными (подмассив) и ненепрерывными (подпоследовательность в строгом комбинаторном смысле) выборками.
Для подготовки к ЕГЭ по информатике эта тема связывает разделы: динамическое программирование, инварианты циклов, оценка сложности, работа с массивами и индексами, арифметика сумм и префиксов, корректность алгоритмов.

Ниже дан системный разбор: формализация задачи, строгие правила корректности и инварианты, семейство алгоритмов (от линейного DP-Кадане до префиксных сумм и O(n log n)-решения для LIS), инженерные соглашения, мини-шпаргалка формул, типичные ошибки и 5 упражнений в стиле ЕГЭ с подробными решениями.

Формальная модель

1. Базовая постановка (максимальная сумма непрерывного подмассива)
   

   Дан массив целых или вещественных чисел

   A = (A[1], A[2], …, A[n]),   n ≥ 1.

   Определим сумму подмассива:

   S(i, j) = ∑_{k=i}^{j} A[k],   1 ≤ i ≤ j ≤ n.

   Требуется найти

   OPT = max_{1 ≤ i ≤ j ≤ n} S(i, j)

   и, как правило, вернуть также границы i* и j*, где достигается максимум (при нескольких решениях – фиксируем соглашение: выбираем решение с наименьшей длиной, затем с минимальным i*, если и это совпадает).

2. Альтернативные постановки
   

   • LIS (Longest Increasing Subsequence) – подпоследовательность по индексу, не обязательно непрерывная, максимальной длины с условием A[i1] < A[i2] < ….

   • Максимальная сумма с ограничением длины: j − i + 1 ≤ L.

   • Максимальная сумма ненепрерывной подпоследовательности: выбрать подмножество индексов с максимальной суммой при дополнительных условиях (например, «никаких двух соседних» – классическая задача «дом с ворами»).

   В данной статье основная линия – непрерывный случай (Кадане), как наиболее частый в обучающих и экзаменационных задачах; LIS приведена как параллельная иллюстрация динамической техники.

Теория корректности: инварианты и эквивалентности

1. DP-формулировка (Кадане): «лучшее окончание на позиции j»
   

   Введём

   dp[j] = max_{1 ≤ i ≤ j} S(i, j)

   – максимальная сумма подмассива, оканчивающегося в j. Тогда верно рекуррентное соотношение:

   dp[1] = A[1]

   dp[j] = max( A[j], dp[j−1] + A[j] )   для j ≥ 2.      (1)

   Инвариант: dp[j] – оптимум среди всех подмассивов, обязательно заканчивающихся в j. Глобальный ответ:

   OPT = max_{1 ≤ j ≤ n} dp[j].                                    (2)

   Доказательство корректности – индукция по j: новый оптимум либо стартует в j (если «выгоднее оборвать»), либо продолжает оптимум на j−1.

2. Индексирование границ
   

   Для восстановления границ достаточно хранить:

   • start[j] – начало оптимального окончания dp[j];

   • «глобальные» i*, j* при обновлении OPT.

   Правило обновления:

   если A[j] ≥ dp[j−1] + A[j], то dp[j] = A[j], start[j] = j

   иначе dp[j] = dp[j−1] + A[j], start[j] = start[j−1]

   Если dp[j] > OPT, то OPT := dp[j]; (i*, j*) := (start[j], j).

3. Эквивалентность с префиксными суммами
   

   Пусть P[0]=0, P[t]=∑_{k=1}^{t} A[k]. Тогда

   S(i, j) = P[j] − P[i−1].

   Задача поиска max_{i≤j} (P[j] − P[i−1]) равносильна:

   OPT = max_{1 ≤ j ≤ n} ( P[j] − min_{0 ≤ t < j} P[t] ).          (3)

   Это даёт альтернативный линейный алгоритм: поддерживать текущий minP = min(P[0..j−1]) и максимум разности.

Алгоритмы и их сложность

1. Кадане (линейный DP, O(n), O(1) памяти без восстановления)
   

   Идея: поддерживать «текущую лучшую сумму, оканчивающуюся здесь» (cur) и «глобальный максимум» (best):

   cur := A[1]; best := A[1]

   for j := 2..n:

     cur := max(A[j], cur + A[j])

     best := max(best, cur)

   return best

   Сложность: Θ(n) времени, Θ(1) памяти.
   Восстановление границ добавляет хранение стартов (см. §2.2), оставаясь линейным.

2. Префиксные суммы (эквивалентный линейный подход)
   

   minP := 0;   P := 0;   best := −∞

   for j := 1..n:

     P := P + A[j]

     best := max(best, P − minP)

     minP := min(minP, P)

   return best

   Плюс: иногда удобнее для добавления ограничений (например, длина не более L: тогда храним минимум префикса «за окном»).

3. Ограничение по длине (скользящее окно на префиксах)
   

   Если 1 ≤ j−i+1 ≤ L, то

   OPT = max_{1 ≤ j ≤ n} ( P[j] − min_{max(0, j−L) ≤ t < j} P[t] ).

   Поддерживаем минимум префикса в окне через монотонную очередь – O(n).

4. LIS (для сравнения техник): O(n log n)
   Вектор «хвостов» tails, где tails[ℓ] – минимально возможный последний элемент возрастающей подпоследовательности длины ℓ. Для каждого x=A[j] бинарно ищем место в tails и обновляем. Возвращаем max ℓ.
   (Подробная LIS не является целью статьи, приведена как иллюстрация к другому классу «подпоследовательностных» задач.)
   

Инженерные правила и соглашения

1. Единая семантика границ. Зафиксируйте предпочтение при равенстве сумм: короче, затем меньший i*. Это делает решение детерминированным.
2. Числовая устойчивость. Для вещественных данных агрегация может аккумулировать ошибки; по возможности используйте Kahan-sum или работайте с целыми.
3. Инициализация на A[1]. Избегайте «минус бесконечности» в языке без безопасных констант; инициализируйте от первого элемента.
4. Один проход – несколько агрегатов. Если одновременно нужно знать минимум/максимум/среднее – рассчитывайте в одном цикле.
5. Проверка «все отрицательные». Кадане корректно возвращает максимум среди отрицательных, но убедитесь, что это ожидаемая семантика (иногда хотят 0 при пустом выборе – тогда адаптируйте формулировку задачи).
6. Восстановление границ. Не забывайте поддерживать start[j]; иначе получите только значение без интервала.
7. Ограничения. Для «длина ≤ L» используйте монотонную структуру для минимума префикса; для «длина = L» используйте разность префиксов фиксированного смещения: S(i, i+L−1) = P[i+L−1] − P[i−1].

Мини-шпаргалка (формулы и псевдокод – «скопировать и использовать»)

1. DP-рекуррент Кадане:
   

   dp[1] = A[1]

   dp[j] = max( A[j], dp[j−1] + A[j] )

   OPT   = max_j dp[j]

2. Префиксы:
   

   P[0]=0,  P[j]=P[j−1]+A[j]

   OPT = max_j ( P[j] − min_{t<j} P[t] )

3. Восстановление границ (Кадане):
   

   если A[j] ≥ cur + A[j]: cur = A[j]; start = j

   иначе cur = cur + A[j]

   если cur > best: best = cur; (i*, j*) = (start, j)

4. С ограничением длины ≤ L:
   

   OPT = max_j ( P[j] − min_{j−L ≤ t < j} P[t] )

5. Оценки сложности: 
   Кадане/префиксы – O(n) времени, O(1) памяти (без восстановления индексов)

Типичные ошибки и их профилактика

• Сброс интервала в неверный момент. Правильно сбрасывать, если начать заново выгоднее: A[j] ≥ cur + A[j].
• Потеря индексов границ. Не хранить start → нельзя восстановить интервал; добавьте поле.
• Неверная инициализация при всех отрицательных. Если цель – «непустой подмассив», инициализируйте от A[1], а не 0.
• Смешение задач. Подпоследовательность (ненепрерывная) ≠ подмассив (непрерывная). Уточняйте формулировку.
• Ошибки в варианте с длиной ≤ L. Нужен минимум префикса в окне, а не минимум массива; используйте монотонную очередь/дек.
• Выход за границы при восстановлении. Внимательно вести i*/j*, особенно при n=1.

Связь с подготовкой к ЕГЭ по информатике

• Динамика и инварианты. Кадане – канонический пример DP с прозрачным инвариантом.
• Асимптотика. Сравнение O(n) (Кадане) и O(n²) (наивный перебор всех интервалов).
• Массивы и индексы. Точное управление границами и восстановление ответа.
• Префиксные суммы. Ещё один ключевой паттерн ЕГЭ, используемый в десятках задач.
• Вариации условий. Умение адаптировать решение под «длина = L», «длина ≤ L», «по модулю», «по чётности» – частые модификации в экзаменационных задачах.

Пять упражнений – с подробными решениями

Упражнение 1. «Корректность рекуррентного шага»
Условие. Докажите, что рекуррентная формула dp[j] = max(A[j], dp[j−1] + A[j]) корректно вычисляет максимальную сумму подмассива, оканчивающегося в j.
Решение. Любой подмассив, оканчивающийся в j, либо состоит из единственного элемента A[j], либо продолжает некоторый оптимальный подмассив, оканчивающийся в j−1. Значит максимум среди таких равен максимуму из этих двух вариантов, что и отражает формула.

Упражнение 2. «Восстановление границ интервала»
Условие. Доработайте линейный алгоритм так, чтобы возвращались индексы i*, j* (при равенстве сумм – выбирайте короче интервал).
Решение (псевдокод):

cur := A[1]; best := A[1]

start := 1;  i* := 1; j* := 1

for j := 2..n:

  if A[j] >= cur + A[j]:

    cur := A[j]; start := j

  else

    cur := cur + A[j]

  end if

  if (cur > best) or (cur = best and (j - start < j* - i*)):

    best := cur;  i* := start;  j* := j

  end if

return (best, i*, j*)

Здесь дополнительное условие обеспечивает детерминированность выбора. 

Упражнение 3. «Префиксы и окно длины ≤ L»
Условие. Для L (натуральное) требуется максимальная сумма подмассива длины не более L. Приведите O(n) решение.
Решение. Пусть P[j] – префиксные суммы. Ищем для каждого j:

best = max( best, P[j] − minP_in_window )

где minP_in_window = min { P[t] : max(0, j−L) ≤ t < j }. Поддерживаем минимум в скользящем окне «монотонной очередью» (дек с неубывателями). Вставляя P[j−1], удаляем элементы с индексом < j−L, вытесняем из хвоста все большие по значению и добавляем текущий. 

Упражнение 4. «Наивный перебор vs Кадане: сравнение сложностей»
Условие. Оцените число операций в наивном переборе всех интервалов и докажите преимущество Кадане.
Решение. Наивный перебор: ∑_{i=1}^{n} ∑_{j=i}^{n} 1 = n(n+1)/2 = Θ(n²) интервалов; даже с префиксами сумм это Θ(n²) обновлений best. Кадане – один проход, Θ(n). Следовательно, при n → ∞ линейный метод асимптотически лучше. 

Упражнение 5. «Все отрицательные элементы: какая должна быть инициализация?»
Условие. Для массива A все элементы отрицательны. Что вернёт корректно реализованный алгоритм Кадане с инициализацией cur := A[1], best := A[1]? Нужно ли менять логику?
Решение. Алгоритм вернёт максимальный (наименее отрицательный) элемент max(A), что совпадает с оптимумом для непустых интервалов. Логику менять не нужно. Если же по постановке допускается «пустой» подмассив с суммой 0 (другая семантика), тогда инициализацию и рекуррент нужно менять: cur := 0, best := 0, а переход – cur := max(0, cur + A[j]). Но это иная задача; важно зафиксировать семантику заранее.

Практика: эталонные фрагменты кода

1. Линейный Кадане с восстановлением границ (Python-стиль)

from typing import List, Tuple 

def max_subarray(a: List[int]) -> Tuple[int, int, int]:

    n = len(a)

    if n == 0:

        raise ValueError("empty array")

    cur = best = a[0]

    start = i_best = j_best = 0

    for j in range(1, n):

        if a[j] >= cur + a[j]:

            cur = a[j]

            start = j

        else:

            cur += a[j]

        # правило детерминированности: короче лучше при равенстве

        if (cur > best) or (cur == best and (j - start < j_best - i_best)):

            best = cur

            i_best, j_best = start, j

    return best, i_best, j_best

2. Префиксная версия с ограничением длины ≤ L (эскиз)

from collections import deque 

def max_subarray_len_leq(a, L):

    P = 0

    best = float("-inf")

    # в деке храним пары (index, prefix) с неубыв. prefix

    dq = deque([(0, 0)])   # P[0]=0 на позиции 0

    for j, x in enumerate(a, start=1):

        P += x

        # удаляем префиксы, вышедшие из окна

        while dq and dq[0][0] < j - L:

            dq.popleft()

        # обновляем ответ

        best = max(best, P - dq[0][1])

        # поддерживаем монотонность для P[j]

        while dq and dq[-1][1] >= P:

            dq.pop()

        dq.append((j, P))

    return best

Чек-лист самопроверки

• Определена семантика: непустой подмассив? (Да/Нет; это влияет на инициализацию.)
• Реализован инвариант dp[j] = max(A[j], dp[j−1] + A[j]).
• При восстановлении границ корректно ведутся start, i*, j*.
• Обработаны крайние случаи: n=1, «все отрицательные».
• Для версий с ограничениями – применены префиксы и монотонные структуры.
• Доказана асимптотика O(n) и объяснено превосходство над O(n²).
• Код не смешивает «подпоследовательность» и «подмассив».

Контрольные вопросы

1. Сформулируйте инвариант Кадане и докажите корректность рекуррентного шага.
2. Выведите эквивалентную префиксную формулу (3) для OPT и объясните, как она приводит к O(n) алгоритму.
3. Как корректно восстанавливать границы i*, j* и зачем вводить правило выбора при равенстве сумм?
4. Чем отличается постановка «непустой подмассив» от «допускается пустой» и как меняется алгоритм?
5. Как адаптировать решение для ограничений на длину интервала?

Заключение

Алгоритм поиска максимальной подпоследовательности (в непрерывной форме – максимальный подмассив) – фундаментальный пример динамического программирования в одной размерности. Его сила – в чётком инварианте, линейной сложности O(n) и простых, но мощных инженерных соглашениях (инициализация, восстановление границ, стабильный выбор при равенствах). Префиксное переосмысление даёт гибкость для ограничений по длине и других вариаций. В контексте ЕГЭ эта тема оттачивает понимание инвариантов, индексации, сложностей и аккуратной реализации – навыков, напрямую конвертируемых в высокие баллы.