407970: GYM102953 7 Maximum Plus Sign

You have an $$$n$$$ by $$$n$$$ 2D grid consisting of $$$n^2$$$ integers. You're trying to find the "plus sign" in the grid with the maximum sum.

You define a "plus sign" to be any contiguous segment of rows (including at least one row), and any contiguous segment of columns (including at least one column). For example, the cells highlighted in blue in the image below are a plus sign:

Your task is to find the sum of the elements of the 2D grid in the plus sign with the maximum sum. For example, the plus sign shown above has a sum of elements of 15.

Note that a valid plus sign doesn't necessarily have to look like a plus sign if it fits the definition above, i.e. the entire grid (a rectangle) would be considered a valid plus sign, as well as a T-shape (if the plus sign included the top row).

The first line of input contains a single positive integer $$$n$$$ $$$(4 <= n <= 400)$$$: the width and height of the 2D grid.

The next $$$n$$$ lines each contain $$$n$$$ space-separated positive integers: the grid. Each grid element will be between $$$-10^9$$$ and $$$10^9$$$, inclusive.

Output a single integer, representing the sum of the elements on the plus sign with the maximum sum in the 2D grid, as defined above.

Subtask 1 (15 points): $$$n <= 40$$$

Subtask 2 (27 points): no additional constraints

5
3 7 -9 8 2
1 -5 3 -4 1
-3 2 0 3 6
-1 -8 5 6 2
4 5 -1 -3 5

34

4
-9 -1 -3 -2
-4 -6 -8 -1
-1 -1 -3 -2
-10 -12 -4 -5

-15