布欧可以把人变成巧克力吃了来增加他的能量，也有可能减少。
现在布欧变了n*m个巧克力，并把巧克力排成一个n*m的矩形，现在布欧想选择一个子矩形，把这个子矩形吃了来增加他的能量，可他不知道选哪个才能使他的能量增加值p最大，布欧也可以选择一个都不吃，这样p
= 0。
现在布欧要你告诉他p的最大值，不然他就先把你变成巧克力吃了！
- 输入
- 第一行：一个整数T 代表测试个数，
接着T组测试数据。对每组测试数据：
第一行：n m 两个整数
接着n行每行m个空格隔开的整数a(i,j)代表对应巧克力的能量值（注意可以是负数，吃了能量减少）1<=n,m<=300
-1000<= a(i,j) <= 1000 - 输出
- T行
每行一个整数 p - 样例输入
-
3 3 3 1 -1 4 2 -2 3 3 -10 1 3 3 -1 -1 -1 -1 -1 -1 -1 -1 -1 3 3 1 1 -10 -1 1 -10 1 1 -10
样例输出
8
0
4
解法：通过把矩阵的每行与下面的每一行压缩成一维数组，然后求最大连续子段和的问题
思想在代码里，通过例子简单的模拟一下就懂
AC code
#include<stdio.h> #include<string.h> int MaxSubstring(int *b,int n)/*求最大连续子段和*/ { int max; int i; int dp; max=0; dp=0; for(i=0;i<n;i++) { if(dp>=0)dp+=b[i]; else dp=b[i]; if(dp>max)max=dp; } return max; } int main() { int T; int i,j,k; int n,m; int a[310][310]; int b[310]; int sum,max; scanf("%d",&T); while(T--) { scanf("%d%d",&n,&m); memset(a,0,sizeof(a)); for(i=0;i<n;i++) for(j=0;j<m;j++) scanf("%d",&a[i][j]); max=0; for(i=0;i<n;i++) { for(k=0;k<m;k++) b[k]=0;/*更新b数组*/ for(j=i;j<n;j++) { for(k=0;k<m;k++) b[k]+=a[j][k];/*压缩处*/ sum=MaxSubstring(b,k); if(sum>max)max=sum; } } printf("%d\n",max); } return 0; }