## 108 - Maximum Sum

Moderator: Board moderators

peterlin
New poster
Posts: 5
Joined: Wed Dec 18, 2002 4:46 pm
Excuse me,
May I ask what's the algo is O(n^3) for this problem ?

Best wishes,
Peter

Ozton
New poster
Posts: 5
Joined: Sun Jan 05, 2003 10:27 am

### Problem 108 Why Time limit exceeded?

WhyWhyWhy???

[c]
#include <stdio.h>

int N, matrix, max_value;

void nbyn_sum(int);
int sum_matrix(int, int, int, int);

int main()
{

int i, j;

while (scanf("%d", &N) == 1) {

max_value = 0;

for (i = 0; i < N; i++)
for (j = 0; j < N; j++) {
scanf("%d", &matrix[j]);
max_value += matrix[j];
}

for (i = N - 1; i > 1; i--)
nbyn_sum(i);

printf("%d\n", max_value);

}

return 0;

}

void nbyn_sum(int nbyn) {

int i, j, k, l, rectangle_sum;

for (i = 0; i <= N - nbyn; i++)
for (j = 0; j <= N - nbyn; j++) {

for (k = i + nbyn - 1; k < N; k++)
for (l = j + nbyn - 1; l < N; l++) {

rectangle_sum = sum_matrix(i, k, j, l);

if (rectangle_sum > max_value)
max_value = rectangle_sum;

}

}

}

int sum_matrix(int start_row, int end_row, int start_col, int end_col) {

int i, j, sum = 0;

for (i = start_row; i <= end_row; i++)
for (j = start_col; j <= end_col; j++)
sum += matrix[j];

return sum;

}
[/c]
Hi~~^^

Ozton
New poster
Posts: 5
Joined: Sun Jan 05, 2003 10:27 am

### [Problem 108] Maximum sum - Compile error...

My FreeBSD gcc or g++ compile no error.
but Online judge compile error.
[c]
#include <stdio.h>

int N, matrix, max_value;

void nbyn_sum(int);
int sum_matrix(int, int, int);

int main()
{

int i, j;

while (scanf("%d", &N) == 1) {

max_value = 0;

for (i = 0; i < N; i++)
for (j = 0; j < N; j++) {
scanf("%d", &matrix[j]);
max_value += matrix[j];
}

for (i = N - 1; i > 1; i--)
nbyn_sum(i);

printf("%d\n", max_value);

}

return 0;

}

void nbyn_sum(int nbyn) {

int i, j, k, l, rectangle_sum;

for (i = 0; i <= N - nbyn; i++)
for (j = 0; j <= N - nbyn; j++) {

rectangle_sum = sum_matrix(i, j, nbyn);

if (rectangle_sum > max_value)
max_value = rectangle_sum;

int tmp = 0;

for (k = j + nbyn; k < N; k++) {

for (l = i; l < nbyn; l++)
tmp += matrix[l][k];

if (rectangle_sum + tmp > max_value)
max_value = rectangle_sum + tmp;

}

tmp = 0;

for (k = i + nbyn; k < N; k++) {

for (l = j; l < nbyn; l++)
tmp += matrix[k][l];

if (rectangle_sum + tmp > max_value)
max_value = rectangle_sum + tmp;

}

}

}

int sum_matrix(int row, int col, int nbyn) {

int i, j, sum = 0;

for (i = row; i < row + nbyn; i++)
for (j = col; j < col + nbyn; j++)
sum += matrix[j];

return sum;

}
[/c]

Hi~~^^

Larry
Guru
Posts: 647
Joined: Wed Jun 26, 2002 10:12 pm
Location: Hong Kong and New York City
Contact:
try putting:

Code: Select all

``````        int tmp = 0;
``````
At beginning of the block..

Ozton
New poster
Posts: 5
Joined: Sun Jan 05, 2003 10:27 am

### ^^

Thanks.
but, Time Limit Exceeded...T.T
Hi~~^^

R
New poster
Posts: 18
Joined: Wed Jan 15, 2003 4:35 pm
well, i think you got it. closing your output with a friendly '\n' is always a good idea. R
New poster
Posts: 18
Joined: Wed Jan 15, 2003 4:35 pm

###  WA

ola,

i think i have solved 108 - but i still get WA.

can someone provide me with additional input/output data to help me track the bug(s) down? or some ideas of extreme cases?

i does 1x1 up to 100x100 tables in a reasonable time (and in fact, i get no timeout ) and it also handles negative values correctly.

i'm stuck thx! R
New poster
Posts: 18
Joined: Wed Jan 15, 2003 4:35 pm
maybe it's a problem of understanding:

"sub-array of size 1x1" means a single element, doesn't it?

R
New poster
Posts: 18
Joined: Wed Jan 15, 2003 4:35 pm
what does your accepted solutions print, when N=0?

*edit*
nah. that shouldn't be a problem, since the problem states
a single positive interger N

R
New poster
Posts: 18
Joined: Wed Jan 15, 2003 4:35 pm
omg, i think i've found it.
The sum of a rectangle is the sum of all the elements in that rectangle.
aaahhh! i thought all the elements on the rectangle and not the ones within.

so
1 1 1
1 1 1
1 1 1
should give 9 and i thought it should be 8.

well, let's see, i will try to rewrite the program and maybe i get an accept then... R
New poster
Posts: 18
Joined: Wed Jan 15, 2003 4:35 pm
accepted! if i just had one example with a maximal sub-rectangle of size 3x3 or greater, that would have saved me 2 hours debugging with one sheet of paper and 30 lines of source-code. we really need a website with more input-data!

epsilon0
Experienced poster
Posts: 112
Joined: Tue Nov 12, 2002 11:15 pm
Location: Paris, France.

### 108 maximum sum

this problem drove me mad for 24 hours. i don't see the O(n^3) solution...

i'll try to code a naive algorithm but i'm sure it will be too slow.

please explain me how it can be solved faster.

the same problem in one dimension (ie a matrix 1xN) has an O(n^2) solution? or better?

HELP
We never perform a computation ourselves, we just hitch a ride on the great Computation that is going on already. --Tomasso Toffoli

epsilon0
Experienced poster
Posts: 112
Joined: Tue Nov 12, 2002 11:15 pm
Location: Paris, France.
ok i solved it in O(n^3) (or so i think)

i found the 0(n) solution for the 1 dim problem and then worked from there.

it ran in 0.031 second on judge's PC.

it would be more like O(n^3 + n) actually (which is about the same anyway)

my concern is about the O(n^3) part, i'm not totally convinced of it's cubicness. We never perform a computation ourselves, we just hitch a ride on the great Computation that is going on already. --Tomasso Toffoli

Larry
Guru
Posts: 647
Joined: Wed Jun 26, 2002 10:12 pm
Location: Hong Kong and New York City
Contact:
Well, the point of the big Oh is that O( n^3 + n ) is O( n^3 ).

It's a nice problem. I got it AC.. though it took me too long.

epsilon0
Experienced poster
Posts: 112
Joined: Tue Nov 12, 2002 11:15 pm
Location: Paris, France.
actually my solution goes like:

loop i from 1 to n
+ loop ii from i to n
+ + loop k from 1 to n
+ + + solve an O(1) problem
+ + solve an O(n) problem

so the complexity would be n(n+1)/2 * (n * 1 + n)
so n^3 + n^2
We never perform a computation ourselves, we just hitch a ride on the great Computation that is going on already. --Tomasso Toffoli