#include <iostream> using namespace std; const int 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; } |
Double click to view unformatted code.