# find sub-matrix with the maximum sum

megha joshi

Ranch Hand

Posts: 206

Ryan McGuire

Ranch Hand

Posts: 1105

7

posted 9 years ago

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 ]

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 ]