POJ-1050-To the Max-normal.txt

/**
 *POJ-1050-To the Max
 *xuchen
 *2015-11-16 19:47:26
**/
#include "stdio.h"
#include <cstring>
#include <cmath>
#include <algorithm>
#include <vector>
#include <queue>
using namespace std;

const int N = 105;
const int MIN = -1e6;
int a[N][N];
int _max;

int calSum(int i, int j, int l)
{
	int sum = 0;
	for(int k=i; k<=j; k++)
	{
		sum+=a[k][l];
	}
	return sum;
}

int solve(int i, int j, int n)
{
	int ans = MIN;
	int sum = MIN;
	for(int l=0; l<n; l++)
	{
		if(sum<0)
		{
			sum = calSum(i, j, l);
		}	
		else
		{
			sum+=calSum(i, j, l);
		}
		ans = max(ans, sum);
	}		
	return ans;
}

int main()
{
	int n;
	scanf("%d", &n);
	for(int i=0; i<n; i++)
		for(int j=0; j<n; j++)
			scanf("%d", &a[i][j]);

	for(int i=0; i<n; i++)
	{
		for(int j=i; j<n; j++)
		{
			_max = max(_max, solve(i, j, n));
		}
	}
	printf("%d\n", _max);
	return 0;
}