108 - Maximum Sum

[Qodeus]

No problem, thank you any way. My formula and yours really comes to the same.

[Solmon K.]

I used O(N^4) algorithm and got AC.

Is there any faster DP algorithm?

[the LA-Z-BOy]

Yes, mine was (as many others) O(N ^ 3).

BTW, what is your complexity of solving maximum sum of One Dimensional array ?

[Solmon K.]

Oh, I see.

[Solmon K.]

Sorry for late understanding..(I'm not good at English. Look at my signature)

I didn't solved any one-dimensional array maximum sum problem..

[emotional blind]

you may solve 507, now,
Its a one dimentional Maximum sum problem.

its time complexity?
O(N)
interesting?
yes it is.

[Solmon K.]

I solved it today.

with time complexity O(N)!

one dimensional array is easy

but

two dimensional array is hard..

[the LA-Z-BOy]

If you can solve ONE-D problem in O(n) then you can do a 2D maximum sum in O(N^3).... Tip: Convert the 2D array to an ONE-D array problem in O(n^2) and you are fine....

[Solmon K.]

I solved it in O(N^3)

with my friend's little help..

[LithiumDex]

Here's my simple solution too 108, it's roughly O((N^4)/4), runs in 1.1~ seconds

Code: Select all

Code Removed ..

I would describe it as "eligant brute force", it checks all possible rectangles, but it accumulates sums to save it from having too sum each rectangle seperatley, thus saving it from being O(N^6)

Edited by : Jan

[emotional blind]

What is your output if all values are negative
I think you have to consider 0*0 subrectangle also
the sum of 0*0 subractangle is always 0, anyway

[LithiumDex]

Well... it says in the description that the minimum sub rectangle size is 1x1,
and I tested it with all negatives -- it works fine (also it is AC)

[emotional blind]

i thought your code was WA code,
so i read it to find what u missed,
and i found only that thing i posted,

(there is another probem in UVA 10827 where
0*0 subractangle should consider.. so mix that on absent mind.. sorry)

But why did you post your ACCEPTED code here?
its not a good practice at all

[kripa82]

Where can I view the input for which my solution failed ? Any insight would be helpful.

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;
}

I assumed positive integer (N) to be any number >=0 . and I tested for corner cases like all negatives, zeros and stuff like tht. I used dp for this.

Thanks

[kripa82]

Got it working with minor changes . didn't initialize max to -128. thnx