Maximum sum submatrix

You are given an $N \times M$ integer matrix. Find a rectangular submatrix (at least one element) with the maximum sum of elements. Print this sum.

The first line contains $N$ and $M$ ($1 \le N, M \le 100$). Each of the next $N$ lines contains $M$ integers ($|a_{i,j}| \le 10^4$).

A single number — the maximum sum.

Checking all rectangles with 2D prefix sums is $O(N^2 M^2) = 10^8$. Faster: choose a top row $r_1$ and a bottom row $r_2$; the column sums over $r_1 \ldots r_2$ ($O(1)$ each with column prefix sums) form a one-dimensional array. Find its maximum subarray with Kadane's algorithm in $O(M)$. In total $O(N^2 M)$.

If all elements are negative, the answer is the largest element. In the first example the answer is $15$: from $(2, 1)$ to $(4, 2)$.

Source: acmp.ru, problem 115, UVa 108.