NYOJ 104-最大和【模板：最大子阵和】

妖狐艹你老母 2022-07-24 08:07 207阅读 0赞

## 最大和 ##

时间限制：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个整数；

输出

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

样例输入

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

样例输出

来源

[\[苗栋栋\]原创][Link 1]

上传者

[苗栋栋][Link 2]

#include<stdio.h>
    #include<string.h>
    #include<algorithm>
    #define MAXN 102
    using namespace std;
    int maxsum(int m,int n,int mat[MAXN][MAXN])
    {
    	int matsum[MAXN][MAXN+1],ret,sum;
    	int i,j,k;
    	for(i=0;i<m;i++)
    	{
    		for(matsum[i][j=0]=0;j<n;j++)
    		{
    			matsum[i][j+1]=matsum[i][j]+mat[i][j];
    		}
    	}
    	for(ret=mat[0][j=0];j<n;j++)
    	{
    		for(k=j;k<n;k++)
    		{
    			for(sum=0,i=0;i<m;i++)
    			{
    				sum=(sum>0?sum:0)+matsum[i][k+1]-matsum[i][j],ret=(sum>ret?sum:ret);
    			}
    		}
    	}
    	return ret;
    }
    int main()
    {
    	int num[MAXN][MAXN];
    	int r,c,t;
    	scanf("%d",&t);
    	while(t--)
    	{
    		scanf("%d%d",&r,&c);
    		for(int i=0;i<r;i++)
    		{
    			for(int j=0;j<c;j++)
    			{
    				scanf("%d",&num[i][j]);
    			}
    		}
    		int ans=maxsum(r,c,num);
    		printf("%d\n",ans);
    	}
    	return 0;
    }

[Link 1]: http://acm.nyist.net/JudgeOnline/search_result.php?source=%5B%E8%8B%97%E6%A0%8B%E6%A0%8B%5D%E5%8E%9F%E5%88%9B
[Link 2]: http://acm.nyist.net/JudgeOnline/profile.php?userid=%E8%8B%97%E6%A0%8B%E6%A0%8B