Maximum Subarray Sum in a 2D Grid

You are given a two-dimensional grid of integers with R rows and C columns. Your task is to find the maximum sum of any contiguous rectangular subgrid within the given grid.

A contiguous subgrid is defined by choosing two rows and two columns (which may be the same) and taking the subgrid that lies between these rows and columns. This problem is a 2D extension of the classic maximum subarray problem, and can be efficiently solved using a dynamic programming approach similar to Kadane's algorithm.

The underlying idea is to fix the left and right column boundaries and reduce the problem to a one-dimensional array for which you can apply Kadane's algorithm. Formally, for a chosen pair of columns l and r, you compute a temporary array temp where

$$\textit{temp}[i] = \sum_{j=l}^{r} grid[i][j]$$

Then, using Kadane's algorithm, you determine the maximum subarray sum of temp. Iterating over all possible column pairs yields the solution.

inputFormat

The first line contains two space-separated integers R and C indicating the number of rows and columns in the grid.

Each of the following R lines contains C space-separated integers representing the grid.

Example:

4 5
1 2 -1 -4 -20
-8 -3 4 2 1
3 8 10 1 3
-4 -1 1 7 -6

outputFormat

Output a single integer which is the maximum sum of any contiguous subgrid.

Example:

29

## sample

4 5
1 2 -1 -4 -20
-8 -3 4 2 1
3 8 10 1 3
-4 -1 1 7 -6

29