800102 - 前缀和——3

一个 n×n 矩阵。要求矩阵中最大加权矩形，即矩阵的每一个元素都有一权值，权值定义在整数集上。从中找一矩形，矩形大小无限制，是其中包含的所有元素的和最大 。

第一行，n，表示矩阵的行列数。

接下来n行，每行n个a_i，表示矩阵各点的权。

对于100%的数据：

1\le n \le 120；

-127 \le a_i \le 127。

最大和子矩阵的和。

样例数据从9到8之间是最大和子矩阵，其和为15。

画图来研究一下二维前缀和的公式是什么？

提示： 与一维前缀和类似，二维前缀和计算的是[1][1]到[r][c]的各项之和。这些项按下标构成了子矩阵。