I have the largest submatrix m1 x n1 of a submatrix m x n. I found how the maximum submatrix sum but I would like to know how to find the coordinates at r1c1 (first row and first column of that submatrix) and r2c2 (last row and last column of that submatrix).
So far I have pre-processed matrix that stores its sums at each element, as in:
SUM[i, j] = SUM[i−1, j] + SUM[i, j−1] − SUM[i−1, i−1] + MATRIX[i, j]
I have found that for any given r1, c1, r2, c2:
SUMS = SUM[r2,c2] - SUM[r1-1,c2] - SUM[r2,s1-1] + SUM[r1-1,c2-1]
How should I approach this problem if I want to get the output that could tell me the coordinates of this submatrix?
You can brute force all possible r1 and r2, then you can again brute force all possible c1 and c2 for this r1, r2 pair and calculate the sum of this submatrix by your SUM array, it's straight forward, but not efficient.
Let's try to improve it. You can know the sum of r1 to r2 for each column in O(1) time by doing some pre-processing. In this way, we turn a 2D largest submatrix problem into a 1D Maximum Subarray Problem which can help us find c1 and c2 for this r1, r2 pair in O(n) time.