Dismiss Notice
Join Physics Forums Today!
The friendliest, high quality science and math community on the planet! Everyone who loves science is here!

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

  1. Sep 8, 2013 #1
    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?
  2. jcsd
  3. Sep 8, 2013 #2

    jim mcnamara

    User Avatar

    Staff: 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.
  4. Sep 8, 2013 #3
    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).
Share this great discussion with others via Reddit, Google+, Twitter, or Facebook