Maximum Sum Subrectangle

You are given a 2D matrix of integers. Your task is to find the subrectangle (a contiguous block of rows and columns) which has the maximum possible sum. A subrectangle is defined by choosing two row indices and two column indices, and considering all the elements in the defined rectangle. An efficient solution applies Kadane's algorithm along with a two‐dimensional scanning technique.

Hint: For a fixed pair of left and right columns, collapse the rows into a 1D array by summing values in each row between these columns and then apply Kadane's algorithm to find the maximum subarray sum. Iterating over all column pairs will result in the optimal answer.

inputFormat

The input is read from stdin and has the following format:

 n m
 a11 a12 ... a1m
 a21 a22 ... a2m
 ...
 an1 an2 ... anm

where n is the number of rows and m is the number of columns. Each of the next n lines contains m space-separated integers representing the matrix.

outputFormat

Output a single integer to stdout which is the maximum sum of any subrectangle in the given matrix.

3 3
1 2 3
4 5 6
7 8 9

45