Kadane 2D и сжатие столбцов — задача «Максимальная сумма прямоугольника» РАЗБОР

Многие алгоритмические задачи имеют красивое одномерное решение, которое потом «поднимается» в двумерное через одну и ту же идеологию: зафиксировать координаты по одной из осей, свернуть задачу в 1D, применить готовый шаблон. Это работает для prefix sums (1D → 2D через формулу включений-исключений), для DP по подсегментам (1D → 2D с парой границ) и — для алгоритма Kadane.

Эта статья разбирает классический шаблон «Kadane 2D» на задаче «Максимальная сумма прямоугольника». Алгоритм собирает несколько полезных техник в одной задаче: одномерный Kadane, сжатие двумерного массива в одномерный за счёт фиксации границ, инкрементальное поддержание сумм по столбцам без полной пересборки на каждом шаге.

---

Что дано

Дана прямоугольная матрица целых чисел размера $N \times M$. Элементы могут быть положительными, нулевыми или отрицательными. Нужно найти прямоугольную подматрицу (подматрицу из подряд идущих строк и столбцов) с максимальной суммой содержащихся в ней элементов.

Подматрица не может быть пустой — нужно выбрать хотя бы одну клетку. Если все элементы матрицы отрицательные, ответом будет наименее отрицательный одиночный элемент.

Ограничения

• $1 \le N, M \le 100$.
• Каждый элемент по модулю не превышает $100$.
• Время — 1 секунда, память — 64 МБ.

Формат ввода

N M
a_{1,1} a_{1,2} ... a_{1,M}
a_{2,1} a_{2,2} ... a_{2,M}
...
a_{N,1} a_{N,2} ... a_{N,M}

Первая строка — два числа $N$ и $M$. Далее $N$ строк по $M$ чисел.

Формат вывода

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

Пример 1

Вход:

2 3
5 0 9
1 2 7

Выход:

24

Подматрица — вся матрица $2 \times 3$. Сумма $5 + 0 + 9 + 1 + 2 + 7 = 24$.

Пример 2

Вход (матрица $4 \times 5$ с отрицательными элементами):

4 5
0 -2 -7 0 -1
9 2 -6 2 0
-4 1 -4 1 0
-1 8 0 -2 1

Выход:

15

Выгодная подматрица — нижняя левая $2 \times 2$ или $3 \times 1$ с положительной суммой. Подбор оптимума глазами на больших матрицах с отрицательными элементами — нетривиален; алгоритм сделает это за нас.

Разберём первый пример руками

Матрица $\begin{pmatrix} 5 & 0 & 9 \\ 1 & 2 & 7 \end{pmatrix}$. Все элементы неотрицательные, значит выгоднее всегда брать всю матрицу — каждый дополнительный элемент только увеличивает сумму. Ответ — $24$.

Этот вырожденный случай (все элементы положительные) показывает, что одномерный Kadane здесь не работает напрямую: он оптимизирует выбор одного подсегмента в одном массиве. Двумерный аналог должен оптимизировать прямоугольник в матрице, причём «прямоугольность» — ограничение, которое не сводится к простому подсегменту.

Идея сведения сложной 2D-задачи к простой 1D — за фиксацию пары границ. Если зафиксировать верхнюю строку $r_1$ и нижнюю строку $r_2$ прямоугольника, остаётся выбрать пару столбцов $c_1, c_2$. Сумма прямоугольника — это сумма элементов из строк $r_1..r_2$ и столбцов $c_1..c_2$. Если для каждого столбца $c$ заранее посчитать «вертикальную сумму» $S[c] = a[r_1][c] + a[r_1+1][c] + \ldots + a[r_2][c]$, то сумма прямоугольника — это просто сумма подсегмента $S[c_1] + S[c_1+1] + \ldots + S[c_2]$ в одномерном массиве $S$.

А максимальная сумма подсегмента в одномерном массиве — это и есть классический одномерный Kadane за $O(M)$. Получается полный алгоритм: перебрать все пары строк (их $O(N^2)$), для каждой пары посчитать $S$ и запустить Kadane.

---

Идея решения: Kadane 2D через сжатие столбцов

Алгоритм в одну фразу.

Перебираем все пары строк $(r_1, r_2)$ с $0 \le r_1 \le r_2 < N$. Для фиксированной пары сжимаем матрицу в одномерный массив $S$ длины $M$, где $S[c]$ — сумма элементов в столбце $c$ от строки $r_1$ до $r_2$ включительно. К $S$ применяем одномерный Kadane — он находит максимальный подсегмент за $O(M)$. Итог — обновляем глобальный ответ.

Одномерный Kadane (база)

Для массива $b$ длины $m$ ищем максимальную сумму непустого подсегмента.

Идея: на каждом шаге $i$ держим лучшую сумму подсегмента, заканчивающегося в $i$ — назовём её cur. На каждой новой клетке у нас два варианта: либо продолжить уже накопленный подсегмент (тогда новый cur = cur + b[i]), либо сбросить его и начать заново с одной клетки (тогда cur = b[i]). Берём максимум — это выгоднее, чем тащить отрицательный префикс. Глобальный максимум best обновляем на каждом шаге.

def kadane(b: list[int]) -> int:
    best = b[0]
    cur = b[0]
    for i in range(1, len(b)):
        cur = max(b[i], cur + b[i])
        best = max(best, cur)
    return best

Сложность: $O(M)$ времени, $O(1)$ памяти (хранится только best и cur).

Инкрементальное сжатие — без полной пересборки $S$

Для фиксированного $r_1$, когда $r_2$ растёт от $r_1$ к $N - 1$, массив $S$ можно поддерживать инкрементально: при переходе от $r_2$ к $r_2 + 1$ добавляем к $S[c]$ значение $a[r_2 + 1][c]$. Не нужно пересчитывать всю сумму с нуля.

Это сэкономит фактор $N$ в общей сложности: внутренний пересчёт $S$ на каждой паре $(r_1, r_2)$ становится $O(M)$, а не $O(N \cdot M)$.

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

Любая прямоугольная подматрица определяется ровно четырьмя границами: $(r_1, r_2, c_1, c_2)$. Алгоритм перебирает все возможные пары $(r_1, r_2)$ — это внешний перебор. Для каждой пары он находит оптимальные $(c_1, c_2)$ — это внутренний Kadane.

Доказательство корректности — конструктивное. Любая оптимальная подматрица имеет какие-то конкретные значения $r_1^*, r_2^*$. Когда внешний перебор дойдёт до пары $(r_1^*, r_2^*)$, в массиве $S$ окажутся именно вертикальные суммы между $r_1^*$ и $r_2^*$. 1D-Kadane найдёт оптимальный подсегмент в $S$ — это именно $c_1^*, c_2^*$ оптимальной подматрицы. Значит, на этой итерации мы пересчитаем best так, что в нём окажется истинный максимум. Алгоритм корректен.

Альтернатива через 2D префиксные суммы

Можно построить 2D-префиксные суммы за $O(N \cdot M)$ один раз, а потом для каждой пары $(r_1, r_2)$ извлекать вертикальную сумму $S[c]$ за $O(1)$ через формулу включений-исключений (та же, что в статье 2 серии «Алгоритмические основы»). Эквивалентно по сложности и чуть прозрачнее теоретически, но чуть длиннее по коду, чем инкрементальное обновление. На $N = M = 100$ оба подхода работают мгновенно — выбор стилевой.

---

Решение: псевдокод

прочитать N, M, матрицу a[N][M]
ans ← -∞

для r1 от 0 до N - 1:
    S[c] ← 0 для каждого c от 0 до M - 1
    для r2 от r1 до N - 1:
        для c от 0 до M - 1:
            S[c] ← S[c] + a[r2][c]
        # 1D Kadane на массиве S
        cur ← S[0]; best ← S[0]
        для c от 1 до M - 1:
            cur ← max(S[c], cur + S[c])
            best ← max(best, cur)
        ans ← max(ans, best)

вывести ans

Сложность: $O(N^2 \cdot M)$ времени, $O(M)$ памяти на массив $S$. Для $N = M = 100$ — $10^6$ операций; укладывается в TL 1 секунда с большим запасом.

---

Код решения

Комментарии по реализации.

• Тип для аккумуляторов. На этой задаче int достаточно ($|\text{сумма}| \le N \cdot M \cdot 100 = 10^6$), но в C++ держим long long для S, cur, best, ans — привычка спасает на чуть более жёстких ограничениях ($|a_{ij}| \le 10^9$ — типичная модификация). В Python int автоматически большой.
• Нейтральный минимум. Python — NEG_INF = float('-inf'), операторы <, > для смешанных int/float работают как ожидается. C++ — LLONG_MIN (или -(long long)1e18).
• (long long)S[c] в max (C++) — явное приведение, чтобы перегрузка max сработала корректно при разных типах операндов. Без него GCC иногда выдаёт ошибку компиляции «no matching function for max(long long, long long&)».
• Кеширование row = a[r2] (Python) в горячем цикле сокращает накладные расходы на индексацию двумерного списка. Без этого a[r2][c] каждый раз делает два обращения; с кешем — одно атомное row[c].
• Быстрый ввод. Python — sys.stdin.buffer.read().split(), на $10^4$ чисел с большим запасом. C++ — ios::sync_with_stdio(false).

---

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

Пример 1: $N = 2, M = 3$, матрица $\begin{pmatrix} 5 & 0 & 9 \\ 1 & 2 & 7 \end{pmatrix}$

Перебор пар строк:

$r_1 = 0, r_2 = 0$: $S = [5, 0, 9]$.

• 1D Kadane: cur = 5; затем $\max(0, 5 + 0) = 5$, best = 5; затем $\max(9, 5 + 9) = 14$, best = 14.
• ans = 14.

$r_1 = 0, r_2 = 1$: $S = [5 + 1, 0 + 2, 9 + 7] = [6, 2, 16]$.

• 1D Kadane: cur = 6; $\max(2, 6 + 2) = 8$, best = 8; $\max(16, 8 + 16) = 24$, best = 24.
• ans = 24.

$r_1 = 1, r_2 = 1$: $S = [1, 2, 7]$.

• 1D Kadane: cur = 1; $\max(2, 1 + 2) = 3$, best = 3; $\max(7, 3 + 7) = 10$, best = 10.
• ans = 24 (не меняется).

Ответ: 24 ✓.

Пример 2: $N = 4, M = 5$, матрица $\begin{pmatrix} 0 & -2 & -7 & 0 & -1 \\ 9 & 2 & -6 & 2 & 0 \\ -4 & 1 & -4 & 1 & 0 \\ -1 & 8 & 0 & -2 & 1 \end{pmatrix}$

Перебор всех $\binom{4}{2} + 4 = 10$ пар строк (включая «один уровень» $r_1 = r_2$). Опустим внутренние Kadane-подсчёты для каждой пары и приведём ключевые наблюдения:

• При $r_1 = 1, r_2 = 3$: $S = [9 - 4 - 1, 2 + 1 + 8, -6 - 4 + 0, 2 + 1 - 2, 0 + 0 + 1] = [4, 11, -10, 1, 1]$. Kadane от $[4, 11, -10, 1, 1]$ — лучший подсегмент $[4, 11]$ с суммой $15$ (продолжать после $-10$ невыгодно: $15 - 10 + 1 + 1 = 7 < 15$).
• Никакая другая пара строк не даёт сумму выше 15 (проверка остальных пар — скучный счёт, опустим).

Ответ: 15 ✓.

---

Крайние случаи

1. $N = M = 1$ — одна клетка

Матрица из одного элемента. Алгоритм инициализирует $S = [a_{0,0}]$, Kadane возвращает $a_{0,0}$, ans равен этому значению. Никаких особых проверок не нужно.

2. Все элементы отрицательные

Например, матрица $\begin{pmatrix} -3 & -1 \\ -2 & -5 \end{pmatrix}$. Здесь оптимальная подматрица — одиночная клетка с наименее отрицательным значением, $-1$.

Корректность проверяется так: 1D-Kadane на массиве из отрицательных чисел возвращает максимум массива. В нашем алгоритме при $r_1 = 0, r_2 = 0, S = [-3, -1]$ — Kadane даёт $\max(-3, -1) = -1$. Это и есть ответ.

Принципиально важно: инициализация cur = S[0], best = S[0], а не cur = 0, best = 0. Если бы мы инициализировали нулём, для всех-отрицательной матрицы алгоритм бы вернул 0 — но «пустая подматрица не разрешена» по условию.

3. Одна строка ($N = 1$) или один столбец ($M = 1$)

При $N = 1$: внешний цикл выполняется только для $r_1 = r_2 = 0$, $S$ совпадает со строкой матрицы, Kadane даёт максимальный подсегмент. Это обычный 1D-Kadane, спрятанный внутри алгоритма.

Аналогично для $M = 1$: $S$ всегда длины 1, Kadane возвращает $S[0]$. Внешний цикл по парам строк просматривает все возможные «вертикальные подмассивы» одного столбца, и ans = max(s) по всем суммам.

4. Максимальные значения

$N = M = 100$, все $a_{ij} = 100$. Сумма всей матрицы — $100 \cdot 100 \cdot 100 = 10^6$. Это укладывается в int32 ($2^{31} \approx 2.1 \cdot 10^9$). На задаче с $|a_{ij}| \le 100$ переполнения нет ни в Python, ни в C++.

5. Матрица из нулей

$S$ всегда нули, Kadane возвращает 0. Ответ — 0.

6. Матрица с одной положительной клеткой среди отрицательных

Например, $\begin{pmatrix} -10 & -10 \\ -10 & 5 \end{pmatrix}$. Все «расширения» в стороны портят сумму, оптимум — одиночная клетка $5$. Корректно через cur = max(b[i], cur + b[i]): при $i = 1$ (новая клетка $5$, после $\text{cur} = -10$) cur = max(5, -10 + 5) = 5, что и нужно.

---

Типичные ошибки

1. Инициализация cur = 0, best = 0 в Kadane. Это даёт неверный ответ для всех-отрицательной матрицы (вернётся 0 вместо наибольшего отрицательного элемента). По условию пустая подматрица не разрешена, поэтому инициализация — обязательно cur = best = b[0].
2. Перебор только подматриц фиксированного размера. Соблазн перебрать все $r_1, r_2, c_1, c_2$ напрямую за $O(N^2 \cdot M^2)$ работает, но при $N = M = 100$ — это $10^8$ операций, на грани TL. Когда внутри ещё нужно посчитать сумму подматрицы (без префиксов — за $O(N \cdot M)$), общая сложность взлетает до $O(N^4 \cdot M^2)$ и точно не проходит.
3. Полная пересборка $S$ на каждой паре $(r_1, r_2)$. Если для каждой пары пересчитывать $S$ суммой $a[r_1][c] + \ldots + a[r_2][c]$ напрямую — это лишний фактор $N$. Инкрементальное обновление S[c] += a[r2][c] при росте $r_2$ — стандартная экономия.
4. int вместо long long в C++ на модификациях задачи. Здесь $|a_{ij}| \le 100$, поэтому int хватает, но в более жёстких версиях ($|a_{ij}| \le 10^9$) int переполняется.
5. Off-by-one в инкрементальном цикле. Цикл for r2 in range(r1, N) должен включать $r_1$ — это случай «подматрица только из одной строки $r_1$». Если написать for r2 in range(r1 + 1, N), потеряется случай однострочной подматрицы и для $N = 1$ ответ окажется $-\infty$.
6. Запутанная индексация в pre-computed prefix sums. Если использовать альтернативу через 2D-префиксные суммы, легко перепутать знаки или сместить индексы на 1. На задачах типа этой инкрементальное обновление $S$ проще и меньше шансов ошибиться.

---

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

• Время: $O(N^2 \cdot M)$. Внешний двойной цикл по $r_1, r_2$ даёт $O(N^2)$ итераций. На каждой — $O(M)$ работа внутри (инкрементальное обновление $S$ + 1D Kadane). Для $N = M = 100$: $10^6$ операций.
• Память: $O(M)$ — массив $S$ длины $M$ + матрица $a$ размером $O(N \cdot M)$.
• Запас по TL: при лимите 1 секунда $10^6$ операций укладывается с большим запасом и в Python, и в C++.

---

Что ещё полезно потренировать

Задачи на ту же идею — Kadane (1D и 2D) и сжатие двумерного массива в одномерный. Все — с возраст-нейтральных платформ.

• Codeforces 327A «Hungry Sequence» или похожие задачи на 1D-Kadane уровня $1100$–$1300$ — для закрепления базового шаблона.
• acmp.ru, раздел «Двумерные массивы» — задачи на работу с подматрицами, 1100–1700.
• Codeforces задачи с тегом dp + implementation уровня $1500$–$1700$, в которых «сведём 2D к 1D» — общая идея, не только Kadane. Например, поиск максимального квадрата из единиц в бинарной матрице.
• Дальше — Kadane с ограничениями. Например, «максимальная сумма подматрицы, не превосходящая $K$» — это уже сложнее ($O(N \cdot M^2 \log M)$ или хитрее), типичная задача уровня $1900$–$2200$.

Для следующего шага — попробовать «обратную» задачу: «минимальная сумма подматрицы», или «количество подматриц с суммой ровно $K$» — комбинация Kadane / prefix sums + hashmap.

---

Итого

• Идея: Kadane 2D = «фиксируем пару строк → сжимаем матрицу в массив сумм по столбцам → запускаем 1D Kadane». Внешний перебор $O(N^2)$, внутренний — $O(M)$. Итог $O(N^2 \cdot M)$.
• Сложность: $O(N^2 \cdot M)$ времени, $O(M)$ памяти на массив $S$ (плюс $O(N \cdot M)$ на матрицу).
• Инкрементальное сжатие: при росте $r_2$ обновлять S[c] += a[r_2][c], не пересчитывать с нуля.
• Ловушки: инициализация Kadane c нуля (ломает случай «всё отрицательное»), забытая итерация $r_2 = r_1$ (потеря однострочных подматриц), полная пересборка $S$ на каждой паре (лишний фактор $N$).
• Связь с другими техниками: prefix sums по столбцам — родственная техника; 1D Kadane — фундамент; «свести 2D к 1D через перебор границ» — общий паттерн, работающий и для других задач (max area, count of submatrices).