2.4 Максимальная сумма подмассива¶

В этой задаче мы рассмотрим классическую проблему алгоритмического анализа — поиск максимальной суммы подмассива. Это отличный пример того, как один и тот же вопрос можно решить алгоритмами с разной асимптотической сложностью: от (O(n^3)) до (O(n)). Идея, заложенная в разработку алгоритма будет описана в следующих главах, но сейчас мы сравним с вами рахные подходы

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

Дан массив из (n) чисел (возможны отрицательные значения). Требуется найти максимальную сумму среди всех непрерывных подмассивов.

Разрешается выбирать пустой подмассив, поэтому ответ всегда не меньше 0.

Пример¶

Пусть дан массив:

3  -2  5  -1  6  -3  2

Максимальную сумму даёт подмассив:

3  -2  5  -1  6

Сумма:

3 - 2 + 5 - 1 + 6 = 11

Ответ: 11

Алгоритм 1 — полный перебор (O(n³))¶

Самый простой способ — перебрать все возможные подмассивы.

Выбрать левую границу a
Выбрать правую границу b
Посчитать сумму элементов между a и b

Реализация¶

int best = 0;

for (int a = 0; a < n; a++) {
    for (int b = a; b < n; b++) {
        int sum = 0;
        for (int k = a; k <= b; k++) {
            sum += array[k];
        }
        best = max(best, sum);
    }
}

cout << best << "\n";

Анализ сложности¶

Три вложенных цикла → O(n³)

Такой алгоритм слишком медленный уже при ($n \approx 5000$).

Алгоритм 2 — улучшенный перебор (O(n²))¶

Можно убрать один цикл.

Идея: если зафиксирована левая граница a, то сумму можно накапливать постепенно при увеличении b.

Реализация второго алгоритма¶

int best = 0;

for (int a = 0; a < n; a++) {
    int sum = 0;
    for (int b = a; b < n; b++) {
        sum += array[b];
        best = max(best, sum);
    }
}

cout << best << "\n";

Почему это быстрее?¶

Теперь для каждой левой границы мы не пересчитываем сумму заново, а просто добавляем следующий элемент.

Сложность¶

Два вложенных цикла → O(n²)

Это уже значительно быстрее, но при (n = 10^5) всё равно будет слишком медленно.

Алгоритм 3 — линейное решение (O(n))¶

Теперь самое интересное: задачу можно решить всего одним проходом по массиву.

Этот алгоритм известен как алгоритм Кадане.

Идея¶

Пусть: $ dp[k] $ — максимальная сумма подмассива, который заканчивается в позиции k.

Для каждого элемента возможны два варианта:

Начать новый подмассив с позиции k
Продолжить предыдущий подмассив

Тогда: $ dp[k] = \max(array[k], dp[k-1] + array[k]) $ Ответ — максимум среди всех dp[k].

Реализация алгоритма¶

int best = 0;
int sum = 0;

for (int k = 0; k < n; k++) {
    sum = max(array[k], sum + array[k]);
    best = max(best, sum);
}

cout << best << "\n";

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

Если текущая накопленная сумма стала отрицательной, то нет смысла её продолжать — лучше начать заново.

Таким образом:

если sum + array[k] хуже, чем просто array[k],
значит старый подмассив только мешает.

Сравнение алгоритмов¶

Алгоритм	Сложность	При n = 100 000
1	O(n³)	невозможно
2	O(n²)	слишком медленно
3	O(n)	мгновенно

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

Общая идея¶

Максимальная сумма подмассива — это:

"Лучший непрерывный участок массива"

Если в какой-то момент накопленная сумма становится отрицательной — её выгоднее отбросить и начать новый участок.

Важное замечание¶

Если пустой подмассив не разрешён, то:

int best = array[0];
int sum = array[0];

for (int k = 1; k < n; k++) {
    sum = max(array[k], sum + array[k]);
    best = max(best, sum);
}

Вывод¶

Задача о максимальной сумме подмассива — классический пример:

как наивный перебор даёт O(n³),
как аккуратная оптимизация уменьшает сложность до O(n²),
и как динамическое программирование позволяет получить O(n).