Разбор задачи «Оптимизация активации нейронного блока»

Идея задачи

Нам дан массив целых чисел a[1..n]. Нужно выбрать непрерывный подмассив с максимальной возможной суммой и вывести эту сумму.

По сюжету задачи каждый элемент массива — это вклад отдельного нейрона в итоговое качество модели:

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

То есть задача сводится к классической:

найти максимальную сумму среди всех непрерывных подмассивов.

Что важно заметить

Полный перебор всех подмассивов слишком дорогой:

• левую границу можно выбрать n способами;
• правую границу тоже n способами;
• всего получается порядка O(n^2) подмассивов.

При n до 2 · 10^5 такой подход не подходит.

Нужен линейный алгоритм O(n).

Ключевое наблюдение

Будем идти слева направо и для каждой позиции знать:

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

Пусть мы сейчас стоим в позиции i и читаем число a[i].

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

1. Начать новый подмассив с элемента a[i].
2. Продлить лучший подмассив, заканчивавшийся в позиции i-1, добавив a[i].

Значит,

bestEndingHere = max(a[i], bestEndingHere + a[i])

После этого обновляем глобальный ответ:

bestOverall = max(bestOverall, bestEndingHere)

Это и есть алгоритм Кадане.

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

Рассмотрим любую позицию i.

Если мы хотим найти лучший подмассив, который оканчивается в i, то его начало может быть только двух типов:

• либо этот подмассив состоит только из a[i];
• либо это некоторый лучший подмассив, заканчивающийся в i-1, к которому мы приписали a[i].

Других вариантов нет, потому что любой подмассив, заканчивающийся в i, либо имеет длину 1, либо получается продлением подмассива, заканчивающегося на предыдущем элементе.

Значит, формула перехода корректна.

А раз на каждом шаге мы поддерживаем максимум среди всех окончаний, то и ответ тоже будет найден корректно.

Разбор на примере

Возьмём массив:

-2 1 -3 4 -1 2 1 -5 4

Будем поддерживать два значения:

• bestEndingHere
• bestOverall

Шаг 1

a[1] = -2

bestEndingHere = -2
bestOverall = -2

Шаг 2

a[2] = 1

bestEndingHere = max(1, -2 + 1) = 1
bestOverall = max(-2, 1) = 1

Шаг 3

a[3] = -3

bestEndingHere = max(-3, 1 + (-3)) = -2
bestOverall = max(1, -2) = 1

Шаг 4

a[4] = 4

bestEndingHere = max(4, -2 + 4) = 4
bestOverall = max(1, 4) = 4

Шаг 5

a[5] = -1

bestEndingHere = max(-1, 4 + (-1)) = 3
bestOverall = max(4, 3) = 4

Шаг 6

a[6] = 2

bestEndingHere = max(2, 3 + 2) = 5
bestOverall = max(4, 5) = 5

Шаг 7

a[7] = 1

bestEndingHere = max(1, 5 + 1) = 6
bestOverall = max(5, 6) = 6

Шаг 8

a[8] = -5

bestEndingHere = max(-5, 6 + (-5)) = 1
bestOverall = max(6, 1) = 6

Шаг 9

a[9] = 4

bestEndingHere = max(4, 1 + 4) = 5
bestOverall = max(6, 5) = 6

Ответ: 6.

Оптимальный подмассив: [4, -1, 2, 1].

Важный крайний случай

Если все числа отрицательные, нельзя вернуть 0, потому что подмассив должен быть непустым.

Например:

-5 -2 -3 -4 -1

Тогда ответ: -1.

Именно поэтому инициализацию нужно делать первым элементом массива, а не нулём.

Алгоритм

1. Считать n.
2. Считать массив.

3. Инициализировать:

   • bestEndingHere = a[0]
   • bestOverall = a[0]

4. Для каждого следующего элемента:

   • пересчитать bestEndingHere = max(a[i], bestEndingHere + a[i])
   • обновить bestOverall = max(bestOverall, bestEndingHere)
5. Вывести bestOverall.

Сложность

• Время: O(n)
• Память: O(1), если не хранить весь массив

Это оптимальное решение для данных ограничений.

Решение на C++

#include <bits/stdc++.h>
using namespace std;

int main() {
    ios::sync_with_stdio(false);
    cin.tie(nullptr);

    int n;
    cin >> n;

    long long x;
    cin >> x;

    long long bestEndingHere = x;
    long long bestOverall = x;

    for (int i = 2; i <= n; i++) {
        cin >> x;

        bestEndingHere = max(x, bestEndingHere + x);
        bestOverall = max(bestOverall, bestEndingHere);
    }

    cout << bestOverall << '\n';
    return 0;
}

Комментарий к решению на C++

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

• лучший подмассив, заканчивающийся здесь;
• лучший ответ на всём префиксе.

Тип long long обязателен, потому что сумма может выйти за пределы int.

Решение на Python

n = int(input())
a = list(map(int, input().split()))

best_ending_here = a[0]
best_overall = a[0]

for i in range(1, n):
    best_ending_here = max(a[i], best_ending_here + a[i])
    best_overall = max(best_overall, best_ending_here)

print(best_overall)

Комментарий к решению на Python

В Python решение записывается особенно компактно. На каждом шаге делается тот же самый выбор:

• либо начать новый подмассив с a[i],
• либо продолжить текущий лучший.

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

1. Инициализация нулём

Неправильно:

best_ending_here = 0
best_overall = 0

Такое решение даст неверный ответ, если все элементы отрицательные.

2. Использование int в C++

При n до 2 · 10^5 и |a[i]| до 10^9 сумма может быть очень большой по модулю, поэтому нужен long long.

3. Попытка решить через префиксные суммы и полный перебор

Даже если суммы подотрезков считать быстро, перебор всех пар границ всё равно даст O(n^2).

Ещё один способ понять идею

Можно мыслить так:

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

Именно это делает формула:

max(a[i], bestEndingHere + a[i])

Она автоматически решает, стоит ли «тащить прошлое» дальше.