#include<stdio.h> int make(int rect[100][100],int begin,int end,int len,int num[]) { for(int j=0;j<len;j++) { int sum=0; for(int i=begin;i<=end;i++) { sum+=rect[i][j]; } num[j]=sum; } return 1; } int main() { int t; scanf("%d",&t); while(t--) { int max=0; int bb=0; int sum=0; int b=0; int len; int num[100]; int rect[100][100]; scanf("%d",&len); for(int i=0;i<len;i++) for(int j=0;j<len;j++) scanf("%d",rect[i]+j); for(int i=0;i<len;i++) { for(int j=i;j<len;j++) { make(rect,i,j,len,num); for(int k=0,l=0;k<len;) { sum=0; b=0; for(l=k;l<len;l++) { if(sum<=-num[i]&&b)break; b=1; sum+=num[l]; if(sum>max||!bb) { max=sum; bb=1; } } k=l+1; } } } if(sum>max||!bb) { max=sum; } printf("%d\n",max); } return 0; } |
Double click to view unformatted code.