View Code of Problem 3569

#include<iostream>
#include<string>
#include<cmath>
#include<cstring>
#include<vector>
#include<iomanip>
#include<cstdio>
#include<algorithm>
#include<ctype.h>
using namespace std;
int num[101][101];
int dp[101];
int main()
{
	long long t;
	cin >> t;
	while (t--)
	{
		int n;
		cin >> n;
		for (int i = 1;i <= n;i++)
		{
			for (int j = 1;j <= n;j++)
			{
				cin >> num[i][j];
			}
		}
		memset(dp, 0, sizeof(dp));
		int max1 = -999;
		for (int i = 1;i <= n;i++)
		{
			int b[101];
			memset(b, 0, sizeof(b));
			for (int j = i;j <= n;j++)
			{
				int k;
				for (k = 1;k <= n;k++)
				{
					b[k] += num[j][k];
					if (dp[k - 1] + b[k] > 0)
						dp[k] = max(dp[k - 1] + b[k], b[k]);
					else
						dp[k] = 0;
					if (dp[k] > max1)
						max1 = dp[k];
				}
			}
		}
		cout << max1 << endl;
	}
}