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

  • Thread starter Jamin2112
  • Start date
  • #1
986
9
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
4,298
2,913
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?

Replies
46
Views
970
Replies
13
Views
2K
  • Last Post
Replies
2
Views
5K
Replies
9
Views
1K
Replies
12
Views
1K
Replies
2
Views
2K
Replies
3
Views
5K
  • Last Post
2
Replies
41
Views
42K
  • Last Post
Replies
11
Views
10K
Top