108 - Maximum Sum

All about problems in Volume 1. If there is a thread about your problem, please use it. If not, create one with its number in the subject.

Moderator: Board moderators

Qodeus
New poster
Posts: 6
Joined: Mon Mar 06, 2006 10:32 pm

Post by Qodeus »

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

Solmon K.
New poster
Posts: 34
Joined: Sun Jun 04, 2006 4:57 am
Location: Busan, Korea

How to solve problem 108??

Post by Solmon K. »

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

Is there any faster DP algorithm?
Sorry for my bad English...

OTL
frustrate

the LA-Z-BOy
Learning poster
Posts: 94
Joined: Wed Jul 31, 2002 12:44 pm
Location: Dacca, Bangladesh
Contact:

Post by 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 ?
Istiaque Ahmed [the LA-Z-BOy]

Solmon K.
New poster
Posts: 34
Joined: Sun Jun 04, 2006 4:57 am
Location: Busan, Korea

...

Post by Solmon K. »

Oh, I see.
Sorry for my bad English...

OTL
frustrate

Solmon K.
New poster
Posts: 34
Joined: Sun Jun 04, 2006 4:57 am
Location: Busan, Korea

.....

Post by 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..
Sorry for my bad English...

OTL
frustrate

emotional blind
A great helper
Posts: 383
Joined: Mon Oct 18, 2004 8:25 am
Location: Bangladesh
Contact:

Post by 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.
New poster
Posts: 34
Joined: Sun Jun 04, 2006 4:57 am
Location: Busan, Korea

...

Post by Solmon K. »

I solved it today. :lol: :lol:

with time complexity O(N)!

one dimensional array is easy

but

two dimensional array is hard..
Sorry for my bad English...

OTL
frustrate

the LA-Z-BOy
Learning poster
Posts: 94
Joined: Wed Jul 31, 2002 12:44 pm
Location: Dacca, Bangladesh
Contact:

Post by 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....
Istiaque Ahmed [the LA-Z-BOy]

Solmon K.
New poster
Posts: 34
Joined: Sun Jun 04, 2006 4:57 am
Location: Busan, Korea

...

Post by Solmon K. »

I solved it in O(N^3)

with my friend's little help..
Sorry for my bad English...

OTL
frustrate

LithiumDex
New poster
Posts: 44
Joined: Tue Jun 06, 2006 6:44 pm
Location: Nova Scotia, Canada
Contact:

108 AC

Post by 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
- Chris Adams

emotional blind
A great helper
Posts: 383
Joined: Mon Oct 18, 2004 8:25 am
Location: Bangladesh
Contact:

Post by 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
New poster
Posts: 44
Joined: Tue Jun 06, 2006 6:44 pm
Location: Nova Scotia, Canada
Contact:

Post by 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)
- Chris Adams

emotional blind
A great helper
Posts: 383
Joined: Mon Oct 18, 2004 8:25 am
Location: Bangladesh
Contact:

Post by 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
New poster
Posts: 3
Joined: Thu Sep 14, 2006 12:37 am

108 - MaximumRectangleSum - WA - Any idea

Post by 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
New poster
Posts: 3
Joined: Thu Sep 14, 2006 12:37 am

Post by kripa82 »

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

Post Reply

Return to “Volume 1 (100-199)”