Finding the maximum-sum sub=rectangle within a matrix

Question

Possible Duplicate:
Getting the submatrix with maximum sum?

Given a 2-dimensional array of positive and negative integers, find the sub-rectangle with the largest sum. The sum of a rectangle is the sum of all the elements in that rectangle. In this problem the sub-rectangle with the largest sum is referred to as the maximal sub-rectangle. A sub-rectangle is any contiguous sub-array of size 1*1 or greater located within the whole array. As an example, the maximal sub-rectangle of the array:

 0 -2 -7  0
 9  2 -6  2
-4  1 -4  1
-1  8  0 -2

is in the lower-left-hand corner:

 9  2
-4  1
-1  8

and has the sum of 15.

So given a rectangle, what will be an efficient algorithm to find the sum of the maximal sub-rectangle (15 in the above example).

Answer 1

You can solve it in O(numCols*numLines^2). Consider the same problem in 1d:

Given a vector of n elements, find the maximum-sum contiguous subsequence.

Let S[i] = maximum sum contiguous subsequence that ends with element i. We have S[1] = array[1] and S[i > 1] = max(S[i - 1] + array[i], array[i]).

Notice that you don't need a vector to solve this, two variables are enough. More here.

Now, for your matrix case, compute Sum[i][j] = sum of the first i elements of column j.

Now, for each possible pair of rows in your matrix, apply the 1d algorithm to the "vector" made from the elements between the rows of your current pair.