#include<stdio.h> int calc(int num[],int begin,int end) { int sum=0; for(int i=begin;i<=end;i++) sum+=num[i]; return sum; } 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 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&&l<len;) { if(!b||num[l]>=0||l<len-1&&max+num[l]>=num[l+1]) { int tmp=calc(num,k,l); if(tmp>max&&b||!b) { max=tmp; b=1; } l++; } else { k=l+1; l=k; } } } } printf("%d\n",max); } return 0; } |
Double click to view unformatted code.