最大和

时间限制：

1000 ms  |  内存限制：

65535 KB

难度：

5

描写叙述

给定一个由整数组成二维矩阵（r*c），如今须要找出它的一个子矩阵，使得这个子矩阵内的全部元素之和最大，并把这个子矩阵称为最大子矩阵。 

样例：

0 -2 -7 0 

9 2 -6 2 

-4 1 -4 1 

-1 8 0 -2 

其最大子矩阵为：

9 2 

-4 1 

-1 8 

其元素总和为15。 

输入

第一行输入一个整数n（0<n<=100）,表示有n组測试数据；

每组測试数据：

第一行有两个的整数r，c（0<r,c<=100），r、c分别代表矩阵的行和列；

随后有r行，每行有c个整数；

输出

输出矩阵的最大子矩阵的元素之和。

例子输入

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

例子输出

15

#include
     
        #include
      
         using namespace std;  #define N 110  int a[N][N];  int b[N];  int main(){    int n,r,c,i,j,k; 	cin>>n;	while(n--){		cin>>r>>c;  		for(i=1;i<=r;++i)          			for(j=1;j<=c;++j)  			{  				cin>>a[i][j];  				a[i][j]+=a[i-1][j];  			}  			int max=a[1][1];  			for(i=0;i<=r-1;++i)  				for(j=i+1;j<=r;++j)  				{  					memset(b,0,sizeof(b));  					for(k=1;k<=c;++k)  					{  						if(b[k-1]>=0)  							b[k]=b[k-1]+a[j][k]-a[i][k];  						else 							b[k]=a[j][k]-a[i][k];  						if(max