http://acm.pku.edu.cn/JudgeOnline/problem?id=1050
Код:
#include <iostream>
using namespace std;
int main()
{
int i,j,k;
int MAX,tmpMAX,tot;
int a[100][100],N;
int column_sum[101][100];
cin >> N;
for(i=0;i<N;i++){
column_sum[0][i]=0;
for(j=0;j<N;j++)
cin >> a[i][j];
}
MAX=a[0][0];
for(i=0;i<N;i++)
for(j=0;j<N;j++)
column_sum[i+1][j]=column_sum[i][j]+a[i][j];
for(i=0;i<N;i++){
for(j=i+1;j<N+1;j++){
tmpMAX=column_sum[j][0]-column_sum[i][0];
tot=0;
for(k=0;k<N;k++){
tot+=column_sum[j][k]-column_sum[i][k];
if(tot>tmpMAX)
tmpMAX=tot;
if(tot<0)
tot=0;
}
if(tmpMAX>MAX)
MAX=tmpMAX;
}
}
cout << MAX << endl;
}