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?
Got a thought to share or found a bug in the code? We'd love to hear from you:
