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; }