题意:给定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 ;
}