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

  • Thread starter Jamin2112
  • Start date
  • #1
986
9

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?
 

Answers and Replies

  • #2
jim mcnamara
Mentor
3,876
2,256
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.
 
  • #3
21
10
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).
 

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

  • Last Post
Replies
4
Views
1K
  • Last Post
Replies
2
Views
5K
Replies
3
Views
5K
Replies
12
Views
1K
Replies
13
Views
1K
  • Last Post
Replies
12
Views
893
Replies
2
Views
2K
  • Last Post
Replies
4
Views
2K
  • Last Post
Replies
1
Views
2K
Top