Maximum Sum Sub Matrix

Problem:

        Given m*n matrix. We have to find a sub-matrix which have maximum sum. Values of the matrix can be both positive and negative.

Idea:

      Lets start with an example then we will generate our idea. Suppose we have 4*4 matrix as below:
    [ initial matrix ] 
-1      2     3      10          
 5      9    -7       6
 0    -1     -3     -5
 7     5   -18       2

Now we add first column with second column. So, the matrix became like this:
-1      1     3      10
 5     14    -7       6
 0    -1     -3     -5
 7    12   -18       2
Now add second column with third column and the third column with last column. Then, the matrix will look like:
-1      1     4      14
 5     14     7      13
 0    -1     -4      -9
 7    12    -6      -4

Now the row addition part. Add first row with second, then add second with third, then third with last. Finally, the matrix will be:
-1      1      4      14
 5     15    11     27
 0     14     7      18
 7     26     1      14

Our matrix is ready to manipulate.

-1	1	4	14
4	15	11	27
4	14	7	18
11	26	1	14

Definitely, we can say form this matrix that value of every cell is the sum of (0,0) to that cell. Say, (1,1) is 15 is the sum of (0,0), (0,1), (1,0) and (1,1) cells that is 15 i.e. ( -1+2+5+9 ) = 15. This property makes our idea easier. 

       In this matrix, the maximum sum is the middle sub-matrix. ( 15 + 11 + 14 + 7 ) = 37.

-1	1	4	14
4	15	11	27
4	14	7	18
11	26	1	14

We are very closer to our solution. Now, see carefully. Cell (2,2) has cumulative sum form cell (0,0) to (2,2).  

-1	1	4	14
4	15	11	27
4	14	7	18
11	26	1	14

We can subtract the sum of cell (0,0) to (0,2) from this result. 

-1	1	4	14
4	15	11	27
4	14	7	18
11	26	1	14

Again, we subtract sum of cell (0,0) to (2, 0) from the last result.

-1	1	4	14
4	15	11	27
4	14	7	18
11	26	1	14

Have we finished ? No. Look at the matrix above carefully. We have subtract cell (0,0) from the actual result  twice. It should be once. Finally, add the (0,0) cell to actual result and we get our maximum sum sub-matrix.