Maximum Sum Submatrix
Given a 2D matrix of integers, find the submatrix with the largest sum. A submatrix is defined by its top-left corner (r1, c1) and its bottom-right corner (r2, c2), where r1 <= r2 and c1 <= c2. The sum of a submatrix is the sum of all elements within its boundaries, inclusive. If there are multiple submatrices with the same maximum sum, return the sum of the submatrix that is lexicographically smallest (i.e., smallest r1, then smallest c1, then smallest r2, then smallest c2).
Input
The first line contains two integers R and C, the number of rows and columns. This is followed by R lines, each containing C integers representing the matrix elements.
Output
Print a single integer, the maximum sum found among all possible submatrices.
Constraints
1 <= R, C <= 400. The matrix elements are integers between -1000 and 1000.
Example 1
9 -2 1 -3 4 -1 2 1 -5 4
6
The subarray [4, -1, 2, 1] has the largest sum = 6.
Example 2
3 1 2 3
6
The subarray [1, 2, 3] has the largest sum = 6.
Hints
# Read the input from stdin and print the answer.
import sys
def main():
data = sys.stdin.read().split()
# your code here
main()
9 -2 1 -3 4 -1 2 1 -5 4
3 1 2 3