Maximum sub-matrix sum

Problem Detail: 

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?

Asked By : saadtaame

Answered By : Ralor

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).

Best Answer from StackOverflow

Question Source : http://cs.stackexchange.com/questions/26328