c++【入门】最大子阵
输入的第一行包含两个整数n,m(1≤n,m≤50),分别表示矩阵 A 的行数和列数。接下来 n 行,每行 m 个整数,表示矩阵 Ai,j(−1000≤Ai,j≤1000)。给定一个 n×m 的矩阵 A,求 A 中的一个非空子矩阵,使这个子矩阵中的元素和最大。其中,A 的子矩阵指在 A 中行和列均连续的一部分。输出一行,包含一个整数,表示 A 中最大的子矩阵中的元素和。内存限制 : 128 MB
·
限制
时间限制 : 1 秒
内存限制 : 128 MB
题目
给定一个 n×m 的矩阵 A,求 A 中的一个非空子矩阵,使这个子矩阵中的元素和最大。其中,A 的子矩阵指在 A 中行和列均连续的一部分。
输入
输入的第一行包含两个整数n,m(1≤n,m≤50),分别表示矩阵 A 的行数和列数。接下来 n 行,每行 m 个整数,表示矩阵 Ai,j(−1000≤Ai,j≤1000)。
输出
输出一行,包含一个整数,表示 A 中最大的子矩阵中的元素和。
样例
输入
3 3 2 -4 1 -1 2 1 4 -2 2
输出
6
代码(优化前)
#include<bits/stdc++.h>
using namespace std;
int a[55][55],ma=INT_MIN;
int main()
{
int n,m;
cin>>n>>m;
for(int i=1;i<=n;i++)
{
for(int j=1;j<=m;j++)
{
cin>>a[i][j];
}
}
for(int x1=1;x1<=n;x1++)
{
for(int y1=1;y1<=m;y1++)
{
for(int x2=x1;x2<=n;x2++)
{
for(int y2=y1;y2<=m;y2++)
{
int sum=0;
for(int i=x1;i<=x2;i++)
{
for(int j=y1;j<=y2;j++)
{
sum+=a[i][j];
}
}
if(sum>ma)
{
ma=sum;
}
}
}
}
}
cout<<ma;
return 0;
}
代码(优化后)
#include<bits/stdc++.h>
using namespace std;
int a[55][55];
int suma[55][55];
int main()
{
int n,m,ma=INT_MIN;
cin>>n>>m;
for(int i=1;i<=n;i++)
{
for(int j=1;j<=m;j++)
{
cin>>a[i][j];
suma[i][j]=suma[i-1][j]+suma[i][j-1]-suma[i-1][j-1]+a[i][j];
}
}
for(int x1=1;x1<=n;x1++)
{
for(int y1=1;y1<=m;y1++)
{
for(int x2=x1;x2<=n;x2++)
{
for(int y2=y1;y2<=m;y2++)
{
int s=suma[x2][y2]-suma[x1-1][y2]-suma[x2][y1-1]+suma[x1-1][y1-1];
if(s>ma)
{
ma=s;
}
}
}
}
}
cout<<ma;
return 0;
}
更多推荐
所有评论(0)