Max Sum Sub Matrix

Given a integer matrix of size m*n. We need to find a sub matrix with the largest sum.

Note:
Negative and Positive numbers are also present.

Solution 1:
List all the Sub Matrices and find the sum of each matrix and then find the maximum sum.

Solution 2:
We construct an output array from the input array in the following manner:
inputArr[m][n] be the input array.
And let us make another array outputArr[m][n] with all fields set to zero by default.
Each element of the array say outputArr[i][j] will store the sum of elements from inputArr[0][0] till inputArr[i][j].

So determine outputArr[i][j] =
inputArr[i][j] + outputArr[i-1][j] + outputArr[i][j-1] - outputArr[i-1][j-1]

Now to find the matrix sum of a matrix starting at i1,j1 till i2,j2 is
sum = outputArr[i2][j2]- outputArr[i1][j2] - outputArr[i2][j1] + outputArr[i1-1][j1-1]

Now we can run an algorithm similar to the first solution only difference is that finding the sum is easier now.

For each sub matrix find the sum and then compare with the maximum sum found till now. Then output the result in the end.