解题思路: 行的前缀和(对行区间求和) + 最大子段原理 (对列区间求和)
注意事项:
参考代码:
#include<stdio.h> #include<string.h> int main() { long int xsum[502][502];//xsum[i][j]前 i 行 j列的前缀和 long int i,j,s,n,m,k; long long int ans,sum=0; memset(xsum,0,sizeof(xsum)); scanf("%ld%ld",&n,&m); for(i=1;i<=n;i++) for(j=1;j<=m;j++) {scanf("%ld",&s); xsum[i][j]=s+xsum[i-1][j];//xsum[i][j]前 i 行 j列的前缀和 } for(i=1;i<=n;i++)//枚举 从 子阵行高 按 最大子段 原理 求和 for(j=i;j<=n;j++) { ans=0; for(k=1;k<=m;k++) {ans+=xsum[j][k]-xsum[i-1][k]; if(ans>sum||sum==0)sum=ans;//先判断 防 全为负数情况 更新 最大值 if(ans<0)ans=0;//当前小于0 则重新开始; } } printf("%lld\n",sum); return 0; }
0.0分
4 人评分
点我有惊喜!你懂得!浏览:2213 |
C语言程序设计教程(第三版)课后习题9.2 (C语言代码)浏览:687 |
程序员的表白 (C语言代码)浏览:1459 |
Biggest Number (C++代码)回溯法浏览:1613 |
C语言训练-求素数问题 (C语言代码)浏览:720 |
输出正反三角形 (C语言代码)格式错误!!!浏览:1140 |
输出正反三角形 (C语言代码)浏览:782 |
C语言程序设计教程(第三版)课后习题1.5 (C语言代码)浏览:470 |
WU-陶陶摘苹果2 (C++代码)浏览:968 |
C语言程序设计教程(第三版)课后习题6.3 (C语言代码)浏览:660 |