【模板】最大子阵和

题目描述

给定一个 $N \times N$ 的二维数组，数组中包含正数和负数。一个子矩阵是指该二维数组中任意相邻的、大小为 $1 \times 1$ 或更大的子数组。子矩阵的和为该子矩阵中所有元素的和。请找出该数组中和最大的子矩阵，并输出其最大和。

输入格式

第一行输入一个正整数 $N$，表示二维方阵的大小。

接下来 $N$ 行，每行包含 $N$ 个整数，表示数组中的元素。

输出格式

输出一个整数，表示最大子矩阵的和。

样例

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

15

样例解释

选择左上角坐标为 $(1,2)$，右下角坐标为 $(4,2)$ 的子矩阵，总和为 $9+2+(-4)+1+(-1)+8=15$。

数据范围

• 对于 $60\%$ 的数据，$1 \le N \le 100$，数组元素范围为 $[-127, 127]$。
• 对于 $100\%$ 的数据，$1 \le N \le 500$，数组元素范围为 $[-127, 127]$。