本文共 1057 字，大约阅读时间需要 3 分钟。

问题描述

给定一个n*m的矩阵A，求A中的一个非空子矩阵，使这个子矩阵中的元素和最大。

其中，A的子矩阵指在A中行和列均连续的一块。

输入

输入的第一行包含两个整数n, m，分别表示矩阵A的行数和列数。

接下来n行，每行m个整数，表示矩阵A。 输出

输出一行，包含一个整数，表示A中最大的子矩阵中的元素个数。

样例

【样例输入】

3 3 -1 -4 3 3 4 -1 -5 -2 8

【样例输出】

10

【样例说明】

取最后一列，和为10。 提示

【数据规模与约定】

对于50%的数据，1<=n, m<=50； 对于100%的数据，1<=n, m<=500，A中每个元素的绝对值不超过5000。

【资源约定】

峰值内存消耗 < 64M CPU消耗 < 3000ms

请严格按要求输出，不要画蛇添足地打印类似：“请您输入…” 的多余内容。

所有代码放在同一个源文件中，调试通过后，拷贝提交该源码。

注意：不要使用package语句。不要使用jdk1.7及以上版本的特性。 注意：主类的名字必须是：Main，否则按无效代码处理。

代码：

#include 
   
     int main(){
   	int n,m;	scanf("%d%d",&n,&m);	int dp[501][501]={
   0};//初始化数组	int i,j;	int t;	for(i=1;i<=n;i++)	{
   		for(j=1;j<=m;j++)		{
   			scanf("%d",&t);			dp[i][j]=dp[i-1][j]+t;//dp存储的是当前所在位置前面的和（例如dp[2][1]=dp[0][0]+dp[1][0]+dp[2][0]）		}	}	/*算法逻辑*/	int temp=0;	int max=-99999;	for(i=1;i<=n;i++)//循环一	{
   		for (j=1;j<=i;j++)//循环二   循环一和循环二实现的是矩阵行的组合		{
   			temp=0;			for(int k=1;k<=m;k++)			{
   				temp=dp[i][k]-dp[j-1][k]+temp;//(dp[i][k]-dp[j-1][k])是第k列第i行到第j行的和				if(temp>max)					max=temp;				if(temp<0)					temp=0;			}		}	}	printf("%d",max);	return 0;}
   

转载地址：http://csrzi.baihongyu.com/