Finding a submatrix with largest sum [duplicate]

This question already has answers here: Closed 11 years ago.

Possible Duplicate:

Finding a submatrix with the maximum possible sum in O(n^2)

I have an NxN matrix. I want to find out an MxM submatrix, with largest sum of its elements, of the above 开发者_高级运维matrix.

What is the efficient algorithm for this.

---

I have an algorithm that runs in constant time when enlarging M and quadratic time when enlarging N.

First submatrix count as usual. Save the sum. Then move one row field right - the two MxM matrices overlap, so you can just just sum the two non overlaping columns. Save all the sums. Now you can choose the largest sum for the line.

Move to next line. Remember the saved sums? The MxM matrices of first and second lines overlap again, so you can just sum the first and the last lines of MxM matrices and compute first sum in second line.

Now move to the second sum of the second line. Do the same thing as above, but you find out that the last lines of first sum and the second sum in the second row overlap again.

I know it is kind of confusing, if you don't get it, let me know I will draw some picture of it. The algorithm is based on paper in this answer.

EDIT: I know I promised picture, but this should be enough:

A  AB   AB   AB   AB   B
AC ABCD ABCD ABCD ABCD BD
AC ABCD ABCD ABCD ABCD BD
AC ABCD ABCD ABCD ABCD BD
AC ABCD ABCD ABCD ABCD BD
 C   CD   CD   CD   CD  D

These are four submatices, A, B, C, D, positioned like this:

AB
CD

First you count the sum of the A submatrix: sum(A). No optimizations here. Now you want to count the sum of B: sum(B). You can do the same as in A, but notice that A and B overlap. So you assign sum(A) to sum(B), count the sum of vertical vector A AC AC AC AC and substract if from sum(B), then count the sum of vertical vector B BD BD BD BD and add it to sum(B).

sum(B) = sum(A) - sum(A AC AC AC AC) + sum(B BD BD BD BD)

You have sum(B). Now you can continue and compute the whole first line of submatices.

Move to the second line: matices C and D. You don't have to sum the whole matice C, because in previous line, you saved sum(A). Notice they overlap again. You just need to add the difference between A and C:

//code (1)
subC = sum([A AB AB AB AB])   //as substract C
addC = sum([C CD CD CD CD])   //as add C
sum(C) = sum(A) - subC + addC

You have sum(C). Now you can get sum(D) like this:

//code (2)
subD = sum([AB AB AB AB B])    //as substract D
addD = sum([CD CD CD CD D])    //as add D
sum(D) = sum(B) - subD + addD 

but compare subD vs. subC and addD vs addC. They overlap! So you can do it this way:

//code (3)
subD = subC - A + B //from subC substract value on A and add B to it
addD = addC - C + D //same as above
sum(D) = sum(B) - subD + addD

You see that instead of 25 aditions for comuting sum of one submatrix, we do 6. For every possible size of MxM, we have MxM aditions for first submatrix, M*2+2 aditions for first row and for first column and 6 aditions for the rest.