Algorithm to find the submatrix with the greatest sum of its elements?

[Jamin2112]

This is a challenge problem I thought of: Given a real-valued matrix A, develop an algorithm that finds the submatrix with the greatest sum of its element. (If there's a tie, just return an arbitrary submatrix that's tied for the win.)

Is there a way other than brute force?

 

[jim mcnamara]

Sounds like an application for dynamic programming. Use Kadane's algorithm on each submatrix using right and left column pairs -

O(n^3). I believe there is a faster algorithm but I do not know it offhand.

 

[ScottSalley]

I've seen this problem before -- Wikipedia calls the 1D problem the "Maximum subarray problem" and it can be solved in O(n). I spent some time trying to find a solution linear in the number of matrix elements, but never found one. I believe the best solution was more than O(n^2) but less than O(n^3) (see the references at the end of the wikipedia article).