Finding a submatrix with the maximum possible sum in O(n^2)

Question

Hi, I'm trying to write a program in Java that when given an MxN matrix it will find the (contiguous) submatrix with the biggest sum of numbers. The program then needs to return the top left corner coordinates of the submatrix and the bottom right corner coordinates. The matrix can include negative numbers and both the matrix and submatrix don't need to be square.

I saw that this was discussed here: http://stackoverflow.com/questions/2643908/getting-the-submatrix-with-maximum-sum and the solution there seems to be O(n^3). A friend of mine said that they had once managed to solve this problem in O(n^2). Also suggested here. Is that possible?

Is there any available code out there that solves this problem in the most efficient way?

Answer 1

You (most likely) can't solve your problem in O(n^2), at least no such algorithm is known. The optimal solution has sub-cubic complexity, but it's very hard to implement and probably slower in practice. You can read a paper about it here.

The usual algorithm used is the O(n^3) one referenced in the question you found.

Answer 2

(S)He's a friend of yours.. so just ask him/her, and do share with us too :)