# Maximum sub-matrix sum

Given a $n\times m$ matrix $A$ of integers, find a sub-matrix whose sum is maximal. If there is one row only or one column only, then this is equivalent to finding a maximum sub-array.

The 1D version can be solved in linear time by dynamic programming. The 2D version can be solved in $\cal O(n^3)$ by looping over all pairs of columns and using the 1D algorithm on the array whose length is the number of rows in the matrix where each position $r$ holds the sum of the elements at row $r$ between the two columns.

If the matrix is given by:

\begin{pmatrix} 1 & -2 & 0 & -1 \\ 5 & 43 & 31 & 78 \\ -45 & -12 & 19 & 9 \end{pmatrix}

Then for the pair of columns $(0,2)$, the max sub-matrix sum can be found by using the 1D algorithm on the array (top to bottom):

\begin{pmatrix} 1-2+0 & = & -1 \\ 5+43+31 & = & 79\\ -45-12+19 & = & -38 \end{pmatrix} Does anybody know of a $\cal O(n^2)$ algorithm for solving this problem?

• Check out this video explaining this question. youtu.be/yCQN096CwWM
– user33438
Commented May 8, 2015 at 1:24
• Can't this be a solved in $O(n^2)$ time by a 2d version of Kadane's algorithm?
– Simd
Commented Dec 20, 2023 at 21:18

I found this: Sung Eun Bae, Sequential and Parallel Algorithms for the Generalized Maximum Subarray Problem. Read pages 18-30, where it says that there are just cubic $$O(nm^2)$$ and sub-cubic algorithms for this problem (in general case), for example Tadao Takaoka's $$O\left(n^3 \sqrt{\frac{\log\log n }{\log n }}\right)$$ algorithm.
I've also found a forum comment saying that this problem can be solved in $$O(N^2\log N )$$ for matrices with N non-zero elements using "funny" segment tree (you can ask commentator about details).