Подматрица с наибольшей суммой

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

В первой строке $N$ и $M$ ($1 \le N, M \le 100$). В каждой из следующих $N$ строк $M$ целых чисел ($|a_{i,j}| \le 10^4$).

Одно число — наибольшая сумма.

Перебор всех прямоугольников с двумерными префиксами — $O(N^2 M^2) = 10^8$. Быстрее: выберите верхнюю строку $r_1$ и нижнюю ; суммы столбцов на участке (за по префиксам столбцов) образуют одномерный массив. В нём наибольший подмассив находится алгоритмом Кадане за . Итого .