解题思路:
1.设一个足够大的二维数组
2.从[1][1]开始向右下累加,使每个位置表示其左上方(包括该位置本身的数)的和
3.四重for循环(前两重与后两重代表两个指针,指示矩阵的左上角和右下角)
4.利用累加好的数组减去矩阵外的数的总和
5.逐个比较得到最大值
注意事项:
*最关键一步在于得到每个子矩阵的具体大小,在减去子矩阵外的总值时,分别减去sum[i-1][t]和sum[k][j-1]位置的值,
但其中已包含了两遍sum[i-1][j-1]位置的值(即该两数值重合累加的部分),因此要加回一次sum[i-1][j-1],这是关键!
参考代码:
#include
using namespace std;
int N,a[105][105],sum[105][105];
int main()
{
cin>>N;
for(int i=1;i<=N;i++)
{
for(int j=1;j<=N;j++)
{
cin>>sum[i][j];
}
}
for(int i=1;i<=N;i++)
{
for(int j=1;j<=N;j++)
{
sum[i][j]+=sum[i-1][j]+sum[i][j-1]-sum[i-1][j-1];
}
}
int a,b,c,d;
int maxi=-999999;
for(int i=1;i<=N;i++)
{
for(int j=1;j<=N;j++)
{
for(int k=i;k<=N;k++)
{
for(int t=j;t<=N;t++)
{
//maxi=max(maxi,sum[k][t]-sum[i-1][t]-sum[k][j-1]+sum[i-1][j-1]);
if(maxi<sum[k][t]-sum[i-1][t]-sum[k][j-1]+sum[i-1][j-1])
{
maxi=sum[k][t]-sum[i-1][t]-sum[k][j-1]+sum[i-1][j-1];
a=i,b=j,c=k,d=t;
}
}
}
}
}
cout<<maxi;
// cout<<a<<" "<<b<<" "<<c<<" "<<d<<endl;
return 0;
}
0.0分
1 人评分
C语言程序设计教程(第三版)课后习题1.5 (C语言代码)浏览:522 |
C语言程序设计教程(第三版)课后习题10.7 (C语言代码)浏览:968 |
C语言程序设计教程(第三版)课后习题1.5 (C语言代码)浏览:513 |
WU-陶陶摘苹果2 (C++代码)浏览:974 |
2006年春浙江省计算机等级考试二级C 编程题(2) (C语言代码)浏览:472 |
水仙花 (C语言代码)浏览:1052 |
1051(奇了怪了)浏览:649 |
演讲大赛评分 (C语言代码)浏览:1636 |
C二级辅导-等差数列 (C语言代码)浏览:695 |
C语言程序设计教程(第三版)课后习题7.4 (C语言代码)浏览:450 |