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.
5 comments:
can you please throw some more light into this solution. like giving an example and running thru it ... i haven't found a good solution to this Q on the net anywhere
output[i2][j2]- output[i2][j1-1]-output[i1-1][j2]+ output[i1-1][j1-1]
kushal
This is O(n^4).
We can use Kadane's 2D algorithm which runs in O(n^3) time.
hi Can You Plz Through Some More Light & if possible try to provide the running code for this
you haven't check boundary condtion when just think whats value of a[-1][-1] nothing how one can solve then
Try to provide algo or program fro this..hope you will help us..
http://stackoverflow.com/questions/2643908/getting-the-submatrix-with-maximum-sum
Post a Comment