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(n^{2})).
This gives a total complexity of O(n^{3})

It may be interesting to think if the complexity can be further reduced to O(n^{2}) 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: