Zoj-1074-To The Max.txt

//ZOJ - 1074-To the _max
#include "stdio.h"
#include <iostream>
#include <cstring>
#include <cstdlib>
#include <cmath>
using namespace std;

const int N = 105;

int dp[N][N];
int _max, n;

void find(int a)
{
	int t=0;
	for(int i=1; i<=n; i++)
	{
		if(t<0)
			t=dp[a][i];
		else
			t+=dp[a][i];
		
		if(t>_max)
			_max=t;
	}
	return;
}


int main()
{
	while(scanf("%d", &n)!=EOF)
	{
		for(int i=1; i<=n; i++)
			for(int j=1; j<=n; j++)
				scanf("%d", &dp[i][j]);
		_max=dp[1][1];
		
		for(int a=1; a<=n; a++)
		{
			find(a);
			for(int b=a+1; b<=n; b++)
			{
				for(int c=1; c<=n; c++)
				{
					dp[a][c]+=dp[b][c];
				}
				find(a);
			}
		}
		
		printf("%d\n", _max);
	}

    return 0;  
}