为了这题 我们首先要了解什么是前缀数组

前缀和

前缀和是一种重要的预处理，能大大降低查询的时间复杂度。可以简单理解为“数列的前n项的和”。

C++ 标准库中实现了前缀和函数 std::partial_sum，定义于头文件 中。

以上内容来自传送门

有兴趣者自便

举个例子

1 2 4 3

5 1 2 4

6 3 5 9

这个数组的前缀数组长这样

1 3 7 10

6 9 15 22

12 18 29 45

这是怎么推的呢，有公式

a[i][j]=a[i-1][j]+a[i][j-1]+a[i-1][j-1];

了解什么是前缀和数组后，开始思路

我们如果把样例数据列出来

可以得到下表

0 0 0 0 1 0 0

0 0 1 0 0 0 0

0 0 0 1 0 0 0

0 0 0 0 0 1 0

0 0 0 0 0 0 1

0 0 0 0 0 0 0

0 0 0 1 0 0 0

0 0 0 0 0 0 0

0 1 0 0 0 0 0

0 0 0 1 0 1 0

0 0 0 1 0 0 0

可以看出是以（1，4）（1，6）（11，4）（11，6）为顶点的长方形和最大（下标从1开始）

那么有一位机智的同学提出问题

小贾，小贾，这和你刚说了一大堆的前缀数组有什么关系？

好，问题提的好，（下次别提了）。

我们来看，如果把刚提到的长方型为一个部分，长方形中的空心为第二部分

你发现了什么？

用前缀数组是不能直接求长方形一圈的和，但可以求整个长方形的和与中间空心的和

两者相减就得出答案

那么只要枚举长方形左上角，右下角的点就可求出最大和

至于为什么可以枚举，因为数据只有100！！

只贴核心代码

for(int i=1;i<=100;i++)

    for(int j=1;j<=100;j++)

        sum[i][j]=sum[i-1][j]+sum[i][j-1]-sum[i-1][j-1]+a[i][j];

计算前缀和

a[i][j]为输入数组

sum为前缀和数组

剩下的只有枚举了

公式在这

/整个长方形/ int j=sum[x2][y2]-sum[x1-1][y2]-sum[x2][y1-1]+sum[x1-1][y1-1];

/空心部分/ int k=sum[x2-1][y2-1]-sum[x1][y2-1]-sum[x2-1][y1]+sum[x1][y1];