內(nèi)部不包含0的最大矩陣和.
#include<cstdio>
#include<algorithm>
#define maxn 1001
#define maxm 1001
#define INF 0x7fffffff
using namespace std;
int n,m;
int sum[maxn][maxm];
int l[maxn][maxn],r[maxn][maxn],h[maxn][maxn],v[maxn][maxn];
int L[maxn][maxn],R[maxn][maxn];
int getsum(int a,int b,int c,int d){
return (sum[c][d]-sum[a-1][d]-sum[c][b-1]+sum[a-1][b-1]);
}
int main(){
freopen("Candy.in","r",stdin);
freopen("Candy.out","w",stdout);
scanf("%d%d",&n,&m);
for (int i=1;i<=n;i++)
for (int j=1;j<=m;j++)
{
scanf("%d",&v[i][j]);
sum[i][j] = sum[i-1][j]+sum[i][j-1]-sum[i-1][j-1]+v[i][j];
}
for (int i=1;i<=n;i++)
{
for (int j=1;j<=m;j++)
if (v[i][j]!=0)
l[i][j] = l[i][j-1]+1;
for (int j=m;j>=1;j--)
if (v[i][j]!=0)
r[i][j] = r[i][j+1]+1;
}
for (int i=1;i<=m;i++)
h[1][i] = 0;
memset(L,63,sizeof(L));
memset(R,63,sizeof(R));
int Answer = -INF;
for (int i=1;i<=n;i++)
for (int j=1;j<=m;j++)
if (v[i][j]!=0)
{
h[i][j] = h[i-1][j]+1;
L[i][j] = min ( l[i][j] , L[i-1][j]);
R[i][j] = min ( r[i][j] , R[i-1][j]);
Answer = max ( Answer , getsum (i-h[i][j]+1,j-L[i][j]+1,i,j+R[i][j]-1) );
}
printf("%d\n",Answer);
return 0;
}