View Code of Problem 3569

// 有一场快乐的新生赛.cpp : 定义控制台应用程序的入口点。
//
#include<stdio.h>
#define N 110
int dp[N][N], a[N][N];
int n,t;
int main()
{
       int i, j, i1, i2;
       int max, sum, tmp;
       while (scanf ("%d", &t) != EOF )
       {
         while(t--)
         {
           scanf("%d",&n);
              for (i = 1; i <= n; i++)
                     for (j = 1; j <= n; j++)
                     {
                       scanf ("%d", &a[i][j]);
                       dp[i][j]=0;
                     }
              for (j = 1; j <= n; j++)
                     for (i = 1; i <= n; i++)
                            dp[j][i] = dp[j][i - 1] + a[i][j];
              max = 0;
              for (i1 = 1; i1 <= n; i1++)
                     for (i2 = i1; i2 <= n; i2++)
                     {
                            tmp = dp[1][i2] - dp[1][i1 - 1];
                            sum = tmp;
                            for (j = 2; j <= n; j++)
                            {
                                   if (sum > 0)
                                          sum += dp[j][i2] - dp[j][i1 - 1];
                                   else sum = dp[j][i2] - dp[j][i1 - 1];
                                   if (tmp < sum) tmp = sum;
                            }
                            if (tmp > max) max = tmp;
                     }
              printf ("%d\n", max);
       }
       }
       return 0;
}