Maximum Rectangle Sum
Given a 2D matrix of integers, find the rectangle with the largest sum of its elements. The rectangle can be of any size, from 1x1 up to the size of the entire matrix. If multiple rectangles have the same maximum sum, choose the one with the smallest top-left row index. If there's still a tie, choose the one with the smallest top-left column index. If there's still a tie, choose the one with the smallest bottom-right row index. If there's still a tie, choose the one with the smallest bottom-right column index.
Input
The first line contains two integers R and C, the number of rows and columns. The following R lines each contain C integers, representing the elements of the matrix.
Output
Print four integers: r1, c1, r2, c2, representing the top-left (r1, c1) and bottom-right (r2, c2) coordinates of the maximum sum rectangle. Coordinates are 0-indexed.
Constraints
1 <= R, C <= 400. The elements of the matrix are between -1000 and 1000.
Example 1
3 3 1 2 -1 -3 5 4 2 -1 3
0 0 2 2
The rectangle from (1,1) to (2,2) has sum 5+4+(-1)+3 = 11, which is the maximum.
Example 2
2 2 -1 -2 -3 -4
0 0 0 0
The largest single element is -1 at (0,0). The tie-breaking rules select the smallest coordinates.
Hints
# Read the input from stdin and print the answer.
import sys
def main():
data = sys.stdin.read().split()
# your code here
main()
3 3 1 2 -1 -3 5 4 2 -1 3
2 2 -1 -2 -3 -4