## 108 - Maximum Sum

Moderator: Board moderators

Qodeus
New poster
Posts: 6
Joined: Mon Mar 06, 2006 10:32 pm
No problem, thank you any way. My formula and yours really comes to the same. Solmon K.
New poster
Posts: 34
Joined: Sun Jun 04, 2006 4:57 am
Location: Busan, Korea

### How to solve problem 108??

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

Is there any faster DP algorithm?

OTL
frustrate

the LA-Z-BOy
Learning poster
Posts: 94
Joined: Wed Jul 31, 2002 12:44 pm
Contact:
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

### ...

Oh, I see.

OTL
frustrate

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

### .....

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..

OTL
frustrate

emotional blind
A great helper
Posts: 383
Joined: Mon Oct 18, 2004 8:25 am
Contact:
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

### ...

I solved it today.  with time complexity O(N)!

one dimensional array is easy

but

two dimensional array is hard..

OTL
frustrate

the LA-Z-BOy
Learning poster
Posts: 94
Joined: Wed Jul 31, 2002 12:44 pm
Contact:
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

### ...

I solved it in O(N^3)

with my friend's little help..

OTL
frustrate

LithiumDex
New poster
Posts: 44
Joined: Tue Jun 06, 2006 6:44 pm
Contact:

### 108 AC

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
A great helper
Posts: 383
Joined: Mon Oct 18, 2004 8:25 am
Contact:
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
Contact:
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
A great helper
Posts: 383
Joined: Mon Oct 18, 2004 8:25 am
Contact:
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

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;
int b;
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 = {
//	{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
Got it working with minor changes . didn't initialize max to -128. thnx