前缀和

上图为二维前缀和的求法,由四个数字求出一个数字

前缀和一般分为三部:

1.将题中所给的数据输入一个maze数组或用x代替

2.用maze数组或者x计算其相对应的sum数组

3.利用sum进行计算

观察到计算公式中有n-1,m-1的情况出现,则可能有数组越界的情况

解决方法是在1/2步的时候用(n和m是长和宽的边界)

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

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

使i,j都为1,留出下标为第0行第0列为0,在计算时正常令i = 0循环,就不越界了

区分前缀和 和 前缀最大值（接雨水问题）（这两个都是数组）