• Post Reply
  • Bookmark Topic Watch Topic
  • New Topic

find sub-matrix with the maximum sum

 
megha joshi
Ranch Hand
Posts: 206
  • Mark post as helpful
  • send pies
  • Quote
  • Report post to moderator
given N x N matrix of positive and negetive intergers. Write some code
that finds the sub-matrix with teh maximum sum of its elements.

Any ideas?


Thanks
 
Ryan McGuire
Ranch Hand
Posts: 1073
4
  • Mark post as helpful
  • send pies
  • Quote
  • Report post to moderator
There's an obvious O(N^6) brute force algorithm.

For each combination of upper left and lower right corners { // O(N^4)
Calculate the sum; // O(N^2)
If the new sum is greater than old maximum, remember it.
}

A question very similar to this in one dimension has an O(N) solution. That makes me think there must be an O(N^2) one for this.
[ October 15, 2007: Message edited by: Ryan McGuire ]
 
  • Post Reply
  • Bookmark Topic Watch Topic
  • New Topic