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

## Main Question or Discussion Point

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?

Related Programming and Computer Science News on Phys.org
jim mcnamara
Mentor
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.

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