#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 人评分