海洋之心


私信TA

用户名:wanggongsheng

访问量:132614

签 名:

等  级
排  名 18
经  验 21668
参赛次数 3
文章发表 163
年  龄 26
在职情况 学生
学  校
专  业 计算机技术

  自我简介:

读研ing,平时不登录dotcpp

#include<cstdio>
#define maxn 520
long long n,m,sum[maxn][maxn],max;
int main(void)
{
	scanf("%lld%lld",&n,&m);
	for(int i=1;i<=n;i++)
	{
		for(int j=1;j<=m;j++)
		{
			scanf("%lld",&sum[i][j]);
			sum[i][j]+=sum[i][j-1];
		}
	}
	/*printf
	for(int i=1;i<=n;i++)
	{
		for(int j=1;j<=m;j++)
		{
			//scanf("%d",&sum[i][j]);
			//sum[i][j]+=sum[i][j-1];
			printf("%d\t",sum[i][j]);
		}
		printf("\n");
	}
	*/
	max=sum[1][1];
	for(int i=1;i<=m;i++)
	{
		for(int j=i;j<=m;j++)
		{
			long long s=0;
			for(int k=1;k<=n;k++)
			{
				
				s+=sum[k][j]-sum[k][i-1];
				if(s>max) max=s; 
				if(s<0) s=0;
			}
		}
	}
	printf("%lld",max);
	return 0;
}

解题思路:

    1.先是一个预处理,然后是进行按照贪心算法计算的,当前面的结果小于0时候,那么则舍弃前面的累加的数值,应为即使加上了,那么也只会让后面的累加的值变小,这样便找不到最大的值。

    2.注意预处理后sum[i][j]表示计算第i行前j个元素的和。



注意事项:
    1.一定要注意顺序 if(s<=0) s=0;  if(s>max) max=s;这两个语句的顺序是不能交换的,不能用一个不存的结果0和之前得到的最大值相比。

 

0.0分

4 人评分

  评论区

  • «
  • »