## 108 - Maximum Sum

Moderator: Board moderators

arnsfelt
New poster
Posts: 44
Joined: Wed Oct 17, 2001 2:00 am
Location: Denmark
Contact:
You start by indexing your arrays from 1. (why ?)
That means your arrays are too small as is.

taj79
Learning poster
Posts: 74
Joined: Sun Jun 09, 2002 11:56 am
Location: India
Contact:
I can't understand what is the problem if I start my array with 1 instead of 0.

The problem is something else
My prog gets stuck when array dim is 4.

cyfra
Experienced poster
Posts: 144
Joined: Thu Nov 22, 2001 2:00 am
Location: Gdynia, Poland

### Hi!

Hi!

taj79: Frankly speaking I have no idea what your program does...
Can you explain me what your algoritm does and what is its time complexity...
Because I don't understand this taj79
Learning poster
Posts: 74
Joined: Sun Jun 09, 2002 11:56 am
Location: India
Contact:
OK i am giving my code again in a proper manner .

Code: Select all

``````[c]

#include<stdio.h>
#include<stdlib.h>
#define MAX 1000

int  sumcol(int A[][MAX],int i,int p,int q);
main()
{ int sum,temp_sum,*u,z,i,j,q,p,t,s,n;
int A[MAX][MAX];

scanf("%d",&n);/* dimension of square matrix */
for(i=1;i<=n;i++)
{
for(j=1;j<=n;j++)
scanf("%d",&A[i][j]);
}
for(i=1;i<=n;i++)
{  printf("\n");
for(j=1;j<=n;j++)
printf(" %d",A[i][j]);
}

sum = A;

for(i=1;i<=n;i++)
for(j=1;j<=n;j++)    /* This 2 loops considers all the elements  */
{printf("\n\n %d %d",i,j);

p=i;
while(p<= n)
{printf("\n Inside while");

if(p == i)
{printf("\np= %d  p==i\n",p);
temp_sum = A[i][j];
if(sum < temp_sum)
sum = temp_sum;
for(q=j+1;q<=n;q++)
{ temp_sum += A[p][q];
if(sum < temp_sum)
sum = temp_sum;
}
printf("\n Max Sum for p = %d is %d\n",p,sum);
++p;
continue;/* Check if this takes back to while   IT WORKS*/
}/* END of p==i  */

printf("\np= %d  p>i\n",p);
u = (int *)malloc(n-j+1 *sizeof(int) );
t=0;
for(q=j;q<=n;q++)
{++t;
*(u + t)= sumcol(A,i,p,q);
printf("    q= %d   sumcol = %d\n",q,*(u + t) );
}
z=*(u+1);
if(z>sum)
sum = z;
for( s=2;s<=t;s++)
{ z += *(u+ s );
if(z>sum)
sum = z;
}
/* printf("\np= %d",p);  */
printf("\n Max Sum for p = %d is %d\n",p,sum);
++p;

}/* END of while(p<= n)  */
}/* END of FOR  */
printf("The largest sum is %d \n",sum);
}

int  sumcol(int A[][MAX],int i,int p,int q)
{
int t,ans =0;
printf("\n Inside sumcol()\n");
for(t=i;t<=p;t++)
{ printf(" %d",A[t][q]);
ans += A[t][q];  }
printf("\n ans = %d\n",ans);
return(ans);
}

[/c]``````
Let me explain my prog
If the input is
0 9 -4 -1
-2 2 1 8
-7 -6 -4 0
0 2 1 -2

The array A is like this
A = 0 A = 9 and so on.
My prog tries to do this

initially it takes 0 ( left most element) as the value of sum variable which is going to give the ans at the end.
it checks the max sum in row 1 of the elements containing A.

Then it considers the elements of row 2 like this.
1st it cosiders sum of A & A
then sum of
A A A A
In the next iteration it also considers A A
and in the next iteration A A are also considered
this way it has checked the rectangle
consisting of A and the other elements in row 1 & 2

Now it will also consider row 3
then row 4
What i m trying to do is finding the maximal sum of the rectangle containing A[j] and A[p][q] 's such that p>=i && q>=j

that's why i have taken

for(i=1;i<=n;i++)
for(j=1;j<=n;j++) /* This 2 loops considers all the elements */

I hope what my prog is trying to do is clear.

But as I run it for the sample problem it gets stuck in between
giving segmentation fault.

cyfra
Experienced poster
Posts: 144
Joined: Thu Nov 22, 2001 2:00 am
Location: Gdynia, Poland
Thanks for explanation...

but I will write you here a simplier (I hope method....

Let us make a table B...

the B[i,j] = sum (from 1 to i and form 1 to j of A)

that means that B[1,1]=A[1,1] B[1,2]:=A[1,1]+A[1,2]; ... B[2,2]= A[1,1]+A[1,2]+A[2,1]+A[2,2]....

and if you have this table the sum of the rectangle for exmple form 2,2 to 4,5 is equal to :
B[4,5]-B[4,1]-B[1,5]+B[1,1] (if you don't believe you can check So if you have table B you can solve this problem in O(n^4) -- check all the possibilities in O(1) time as I wrote before...

If you are clever you can count the B table in O(n^2) time...
because B[i,j]:=b[i-1,j]+b[i,j-1]-b[i-1,j-1]+a[i,j] ...

And the whole program complexity is O(n^4)..

Try to implement this (this is quite an easy algoritm so try it )

Good Luck taj79
Learning poster
Posts: 74
Joined: Sun Jun 09, 2002 11:56 am
Location: India
Contact:
As per cytra's suggestion I have written a new prog.
But the judge says{b] wrong answer[/b]
I can't see anything wrong.

[c]

/* doing the prob using the algo given by cytra
http://acm.uva.es/board/viewtopic.php?p=2709#2709 */
#include<stdio.h>
#include<stdlib.h>
#define MAX 100

main()
{ int sum,i,j,q,p,t,n,k,l,maxsum,i1,j1,k1,l1,row,col;
int A[MAX][MAX],B[MAX+1][MAX+1];

scanf("%d",&n);/* dimension of square matrix */
for(i=1;i<=n;i++)
{
for(j=1;j<=n;j++)
scanf("%d",&A[j]);
}
/* for(i=1;i<=n;i++)
{ printf("\n");
for(j=1;j<=n;j++)
printf(" %d",A[j]);
} */
for(i=0;i<=n;i++)
B = 0;
for(j=1;j<=n;j++)
B[j] = 0;
for(i=1;i<=n;i++)
for(j=1;j<=n;j++)
{
B[j] = 0;
for(p=1;p<=i;p++)
for(q=1;q<=j;q++)
B[j] += A[p][q];
}
/* printf("\n The table B: \n");
for(i=1;i<=n;i++)
{ printf("\n");
for(j=1;j<=n;j++)
printf(" %d",B[j]);
}
printf("\n"); */
maxsum = A;
for(i=1;i<=n;i++)
for(j=1;j<=n;j++)
for(k=i;k<=n;k++)
for(l=j;l<=n;l++)
{ sum =0;
if( i==k && j==l)
sum = A[j];
else if( i == k && j != l)
for(col = j;col<= l;col++)
sum += A[col];
else if( i != k && j == l)
for(row = i;row <= k;row++)
sum += A[row][j];
else
sum = B[k][l] - B[k][j-1] - B[i-1][l] +B[i-1][j-1];
/* printf("\n i=%d j=%d k=%d l=%d sum=%d",i,j,k,l,sum); */
if(maxsum < sum)
{i1 =i;j1=j;k1=k;l1=l;
maxsum = sum;
}
}
printf("\n%d",maxsum);
/* printf("\n i = %d j=%d k=%d l=%d ",i1,j1,k1,l1); */

}

[/c]

cyfra
Experienced poster
Posts: 144
Joined: Thu Nov 22, 2001 2:00 am
Location: Gdynia, Poland
Hi!

But you have some small mistakes in your program....

I have changed some things and got AC.

I will send you it on PM..

Good Luck mystical_liu
New poster
Posts: 9
Joined: Sun Jul 21, 2002 1:18 pm

### 108 - Maximum Sum

this is my code!~!
and the judge say limit!!!
is there anybody can help me ???
[cpp]#include<stdio.h>
int in,arr={0},max=0,count;
int cou(int i,int j,int x,int y)
{
int a,b;
count=0;
for(a=i;a<=x;a++)
for(b=j;b<=y;b++)
count+=arr[a];
if(count>max)max=count;
}
void search()
{
int i,j,x,y;
for(i=0;i<in;i++)
{
for(j=0;j<in;j++)
{
for(x=i;x<in;x++)
{
for(y=j;y<in;y++)
{
cou(i,j,x,y);
}
}
}
}
}
main()
{
int i,j;
while(scanf(" %d",&in)==1)
{
for(i=0;i<in;i++)
for(j=0;j<in;j++)
{
scanf(" %ld",&arr[j]);
if(arr[j]>max)max=arr[j];
}
search();
printf("%d\n",max);
}
}
[/cpp]

Dominik Michniewski
Guru
Posts: 834
Joined: Wed May 29, 2002 4:11 pm
Location: Wroclaw, Poland
Contact:
try to use Dynamic Programming
exist solution for this problem which work with O(n^3) time .... or strong optimize your code to O(n^4) - it's in a lot of times acceptable too

Best regards

pc5971
New poster
Posts: 34
Joined: Mon Aug 05, 2002 11:24 am
Contact:
I tried something like Dynamic Programming but it doesn't work. I don't know why here is the source. Maybe you can help me...

Code: Select all

``````[pascal]
program p108(input,output);
var t:array[1..100,1..100] of integer;
a:array[1..2,1..100] of integer;
k,l,n,max,cd,i,j,p:integer;
s,s1:string;
x:1..2;

begin
i:=1; j:=1;
repeat
while s=' ' do delete(s,1,1);
while s[length(s)]=' ' do delete(s,length(s),1);
repeat
k:=1;
if s='-' then begin
k:=-1;
delete(s,1,1);
end;
while (s in ['0'..'9']) and (length(s)>0) do
begin
t[i,j]:=t[i,j]*10+ord(s)-ord('0');
delete(s,1,1)
end;
t[i,j]:=k*t[i,j];
while s=' ' do delete(s,1,1);
if j<n then j:=j+1
else
begin
j:=1; i:=i+1;
end;
until length(s)=0;
until (i=n+1) and (j=1);
max:=t[1,1];
for i:=1 to n do
for j:=1 to n do
begin
x:=1;
a[1,j]:=t[i,j];
for k:=j+1 to n do
a[1,k]:=a[1,k-1]+t[i,k];
for k:=i+1 to n do
begin
a[3-x,j]:=a[x,j]+t[k,j];
if a[3-x,j]>max then
max:=a[3-x,j];
for l:=i+1 to n do
begin
a[3-x,l]:=a[3-x,l-1]+a[x,l]-a[x,l-1]+t[k,l];
if a[3-x,l]>max then
max:=a[3-x,l];
end;
x:=3-x;
end;
end;
write(max);
end.
[/pascal]``````
Thank you

pc5971
New poster
Posts: 34
Joined: Mon Aug 05, 2002 11:24 am
Contact:
There was a fullish mistake. I just found it...
[pascal]
program p108(input,output);
var t:array[1..100,1..100] of integer;
a:array[1..2,1..100] of integer;
k,l,n,max,cd,i,j,p:integer;
s,s1:string;
x:1..2;

begin
i:=1; j:=1;
repeat
while s=' ' do delete(s,1,1);
while s[length(s)]=' ' do delete(s,length(s),1);
repeat
k:=1;
if s='-' then begin
k:=-1;
delete(s,1,1);
end;
while (s in ['0'..'9']) and (length(s)>0) do
begin
t[i,j]:=t[i,j]*10+ord(s)-ord('0');
delete(s,1,1)
end;
t[i,j]:=k*t[i,j];
while s=' ' do delete(s,1,1);
if j<n then j:=j+1
else
begin
j:=1; i:=i+1;
end;
until length(s)=0;
until (i=n+1) and (j=1);
max:=t[1,1];
for i:=1 to n do
for j:=1 to n do
begin
x:=1;
a[1,j]:=t[i,j];
for k:=j+1 to n do
a[1,k]:=a[1,k-1]+t[i,k];
for k:=i+1 to n do
begin
a[3-x,j]:=a[x,j]+t[k,j];
if a[3-x,j]>max then
max:=a[3-x,j];
for l:=j +1 to n do
begin
a[3-x,l]:=a[3-x,l-1]+a[x,l]-a[x,l-1]+t[k,l];
if a[3-x,l]>max then
max:=a[3-x,l];
end;
x:=3-x;
end;
end;
write(max);
end.
[/pascal]

Bye

Dominik Michniewski
Guru
Posts: 834
Joined: Wed May 29, 2002 4:11 pm
Location: Wroclaw, Poland
Contact:
It's not easy for me to explain correct this algorithm of DP (poor englich ) but I try to write a solution today afternoon ....

y,x = coordinate of matrix Idea is:
1. for each y find biggest sum in every row, and update max (you check in this way all matrix of size 1 x N) - linear algorithm exists for this job - something like text searching, I forgot it name 2. add row i+1 to row i for each i in 1..N and do step 1 (all matrix 2 x N)
and so on ....
Maybe this hint help our ....

Greetings
Dominik

PS. PC5971- I don't analize your code (not enough time ) but if you correct implement specified algorithm, you could get complexity O(n^3)

PS. (Both of you) What about matrix, which have all values set to max (100, if I remember) ? Integer is not enough, isn't it ?

21743NX
New poster
Posts: 9
Joined: Tue Aug 27, 2002 8:39 am

### 108 Maximum sum WA

It is a standard piece of code. Why W.A.

Hi. My name is Kassey

I got all the sample input correct
yet my code got a W.A answer

what is wrong???

Code edited away.

Last edited by 21743NX on Tue Sep 24, 2002 11:43 am, edited 1 time in total.

arnsfelt
New poster
Posts: 44
Joined: Wed Oct 17, 2001 2:00 am
Location: Denmark
Contact:
Change these line
[cpp]
while (cin)
{
cin >> N;
[/cpp]

to

[cpp]
while (cin >> N)
[/cpp]

21743NX
New poster
Posts: 9
Joined: Tue Aug 27, 2002 8:39 am
Thanks alot man