Maximum sum/area submatrix

Question

Input: nxn matrix of postitive/negative numbers and k.

Output: submatrix with maximum sum of its elements divided by its number of elements that has at least k elements.

Is there any algorithm better than O(n^4) for this problem?

http://stackoverflow.com/questions/2643908/getting-the-submatrix-with-maximum-sum read this — Mateusz, Oct 26 '12 at 19:59
This question has a trivial answer: just find the maximal element of the matrix. A 1x1 sub-matrix, containing this element is the maximum sum/area sub-matrix. — Evgeny Kluev, Oct 26 '12 at 20:18
@EvgenyKluev You are right. What if we look for matrices with more than k elements. — Mohammad Moghimi, Oct 26 '12 at 20:29
For more than k elements, you can try all sub-sets of columns and solve 1-dimensional version of this problem as described in [this question](http://stackoverflow.com/q/12128221/1009831). — Evgeny Kluev, Oct 26 '12 at 20:33

score 1 · Answer 1 · answered Oct 06 '13 at 00:38

1

An FFT-based divide-and-conquer approach to this problem:

https://github.com/thearn/maximum-submatrix-sum

It's not as efficient as Kadane's, (O(N^3) vs. O(N^3 log N)) but does give a different take on solution construction.

answered Oct 06 '13 at 00:38

thearn

323
3
6

This is pretty impressive. – jwalk Jan 08 '16 at 20:10

score 0 · Answer 2 · answered Jul 14 '13 at 19:37

There is a O(n^3) 2-d kadane algorithm for finding the maximum sum submatrix (i.e. subrectangle) in an nxn matrix. (You can find posts on SO about it, or read online). Once you understand how the algorithm works, it is clear that you can get an O(n^3) time solution for your problem if you can solve the problem of finding a maximum average subinterval of length at least m in a 1-d array of n numbers in O(n) time. This is indeed possible, see the paper cs.slu.edu/~goldwasser/publications/DensityPreprint.pdf

Thus there is an O(n^3) time solution for your problem.

Maximum sum/area submatrix

2 Answers2