Make delicious recipes!

Find submatrix with largest sum in a given 2D matrix of integers



Solution: Before attempting this problem, it is important to be familiar with kadane's algorithm.
Kadane's algorithm finds sub-array with maximum sum in O(n) for 1D arrays.
The same algorithm can be run inside two loops to work for 2D array in this case.

Example:

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


For the above matrix, the largest sum submatrix is:

 9 2
-4 1
-1 8



Code:

int findMaxSum (int matrix[numRows][numCols])
{
    int maxSum=0;
 
    for (int left = 0; left < numCols; left++)
    {
        int temp[numRows] = {0};
 
        for (int right = left; right < numCols; right++)
        {
            // Find sum of every mini-row between left and right columns and save it into temp[]
            for (int i = 0; i < numRows; ++i)
                temp[i] += matrix[i][right];
 
            // Find the maximum sum subarray in temp[].
            int sum = kadane(temp, numRows);
 
            if (sum > maxSum)
                maxSum = sum;
        }
    }
 
    return maxSum;
}


How the algorithm executes:




Basically, kadane's algorithm (complexity: O(n)) is used inside a naive maximum sum sub-array problem (complexity: O(n2)).
This gives a total complexity of O(n3)

It may be interesting to think if the complexity can be further reduced to O(n2) if we can apply kadane's algorithm to the outer two loops too?




Like us on Facebook to remain in touch
with the latest in technology and tutorials!


Got a thought to share or found a
bug in the code?
We'd love to hear from you:

Name:
Email: (Your email is not shared with anybody)
Comment:

Facebook comments:

Site Owner: Sachin Goyal