1074.cpp

acm.zju.edu.cn第1074,1005,1010题

#include <iostream>
using namespace std;
int table[101][101];

int main()
{
	int n, temp[101], max(0), sum(0);
	for(int i = 0; i < 101; i++)
		{
			table[i][0] = 0;
			table[0][i] = 0;
		}
	
	while(cin >> n)
	{
		max = 0;
		
		for(int i = 1; i <= n; i++)
			for(int j = 1; j <= n; j++)
			{
				cin >> table[i][j];
		        table[i][j] += table[i - 1][j];
			}
	
		for(int i = 1; i  <= n; i++)
			for(int j = i; j <= n; j++)
			{
				sum = 0;
				for(int k = 1; k <= n; k++)
					temp[k] = table[j][k] - table[i - 1][k];
				for(int m = 1; m <= n; m++)
				{
					if(sum + temp[m] >= 0)
					{
						sum += temp[m];
						if(sum >= max)
							max = sum;
					}
					else
						sum = 0;
				}
			}
		cout << max << endl;
	}
	return 0;
}