This week's book giveaway is in the Servlets forum.
We're giving away four copies of Murach's Java Servlets and JSP and have Joel Murach on-line!
See this thread for details.
The moose likes Programming Diversions and the fly likes find sub-matrix with the maximum sum Big Moose Saloon
  Search | Java FAQ | Recent Topics | Flagged Topics | Hot Topics | Zero Replies
Register / Login


Win a copy of Murach's Java Servlets and JSP this week in the Servlets forum!
JavaRanch » Java Forums » Other » Programming Diversions
Bookmark "find sub-matrix with the maximum sum" Watch "find sub-matrix with the maximum sum" New topic
Author

find sub-matrix with the maximum sum

megha joshi
Ranch Hand

Joined: Feb 20, 2007
Posts: 206
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

Joined: Feb 18, 2005
Posts: 1006
    
    3
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 ]
 
I agree. Here's the link: http://aspose.com/file-tools
 
subject: find sub-matrix with the maximum sum
 
Similar Threads
WA #1.....word association
Maximum Sum Project!!
Aaah, the beauty, the elegance...
JAVA-Synchronization -VERY beginner-Help
The question