OJ Board

Code: Select all

Code Removed ..

Code: Select all

/* Maximum sum */

#include <iostream>
#include <vector>

using namespace std;

class MaximumRectangleSum
{
	int a[100][100];
	int b[100][100];
	int max, sum;
	int n;
public:
	void Init();
	int ComputeMaximumSum(void);
	bool IsValidIndex(int i, int j);
};

bool MaximumRectangleSum::IsValidIndex(int i, int j)
{
	if(i >= 0 && i < n && j >= 0 && j < n) return true;
	return false;
}

void MaximumRectangleSum::Init()
{
	int leftabove = 0, upabove = 0, diagonalabove = 0;
	while(cin >> this->n)
	{
		max = 0;
		for(int i = 0; i < n; ++i)
		{
			for(int j = 0; j < n; ++j)
			{
				leftabove = 0, upabove = 0, diagonalabove = 0;
				b[i][j] = 0;
				cin >> this->a[i][j];
				if(IsValidIndex(i, j-1))
					leftabove = b[i][j-1];
				if(IsValidIndex(i-1, j))
					upabove = b[i-1][j];
				if(IsValidIndex(i-1, j-1))
					diagonalabove = b[i-1][j-1];
				b[i][j] = leftabove + upabove - diagonalabove + a[i][j];
				if(b[i][j] > max) max = b[i][j];
			}
		}
		cout << ComputeMaximumSum() << endl;
	}
}

int MaximumRectangleSum::ComputeMaximumSum()
{
	for(int w = 1; w < n; ++w)
	{
		for(int x = 0; x < n; ++x)
		{
			for(int y = 1; y < n; ++y)
			{
				for(int z = x; z < n; ++z)
				{
					sum = b[y][z];
					if(IsValidIndex(y, x-1))
						sum -= b[y][x-1];
					if(IsValidIndex(w-1, z))
						sum -= b[w-1][z];
					if(IsValidIndex(w-1, x-1))
						sum += b[w-1][x-1];
					if(sum > max) max = sum;
				}
			}
		}
	}
	return max;
}

void Start1()
{
	//int a[4][4] = {
	//	{0, -2, -7, 0},
	//	{9, 2, -6, 2},
	//	{-4,  1, -4,  1},
	//	{-1, 8, 0, -2}
	//};
	//int n = 4;
	MaximumRectangleSum p;
	//p.Init(a, n);
	p.Init();
}

//TODO
int main()
{
	Start1();
	return 0;
}