POJ 1050 To the Max (最大子矩阵和)

题目链接

题意:给定N*N的矩阵,求该矩阵中和最大的子矩阵的和。

题解:把二维转化成一维,算下就好了。

#include <cstdio>
#include <cstring>
#include <algorithm>
using namespace std;
typedef long long ll;
const ll N=1e3+;
ll ans=-,tmp,data[N][N],a[N];
int ansi1=,ansj1=,ansi2=,ansj2=,tmp1=,tmp2=,n,m;
int main()
{
while(scanf("%d",&n)!=EOF){
m=n; ans=-;
memset(data,,sizeof(data));
for(int i=;i<=n;i++)
for(int j=;j<=m;j++){
scanf("%lld",&data[i][j]);
data[i][j]+=data[i-][j];
}
for(int i=;i<=n;i++)
for(int k=;k<i;k++)
{
memset(a,,sizeof(a));
tmp=;
for(int j=;j<=m;j++){
a[j]=data[i][j]-data[k][j];
tmp+=a[j];
tmp=max(tmp,0LL);
ans=max(ans,tmp);
}
}
printf("%lld\n",ans);
}
return ;
}
上一篇:在opencv3中实现机器学习算法之:利用最近邻算法(knn)实现手写数字分类


下一篇:Oracle重做日志恢复数据模拟实验