108 - Maximum Sum

[arnsfelt]

You start by indexing your arrays from 1. (why ?)
That means your arrays are too small as is.

[taj79]

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]

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]

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[1][1];

   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[1][1] = 0 A[1][2] = 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[1][1].

Then it considers the elements of row 2 like this.
1st it cosiders sum of A[1][1] & A[2][1]
then sum of
A[1][1] A[2][1] A[1][2] A[2][2]
In the next iteration it also considers A[1][3] A[2][3]
and in the next iteration A[1][4] A[2][4] are also considered
this way it has checked the rectangle
consisting of A[1][1] 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]

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]

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.
Could anyone please help me

[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] = 0;
for(j=1;j<=n;j++)
B[0][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[1][1];
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]

Hi!

Your idea was OK! ..

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]

this is my code!~!
and the judge say limit!!!
is there anybody can help me ???
[cpp]#include<stdio.h>
int in,arr[200][200]={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]

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]

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
  readln(n);
  i:=1; j:=1;
  repeat
      readln(s);
      while s[1]=' ' do delete(s,1,1);
      while s[length(s)]=' ' do delete(s,length(s),1);
      repeat
        k:=1;
        if s[1]='-' then begin
          k:=-1;
          delete(s,1,1);
        end;
        while (s[1] in ['0'..'9']) and (length(s)>0) do
          begin
            t[i,j]:=t[i,j]*10+ord(s[1])-ord('0');
            delete(s,1,1)
          end;
        t[i,j]:=k*t[i,j];
        while s[1]=' ' 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]

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
readln(n);
i:=1; j:=1;
repeat
readln(s);
while s[1]=' ' do delete(s,1,1);
while s[length(s)]=' ' do delete(s,length(s),1);
repeat
k:=1;
if s[1]='-' then begin
k:=-1;
delete(s,1,1);
end;
while (s[1] in ['0'..'9']) and (length(s)>0) do
begin
t[i,j]:=t[i,j]*10+ord(s[1])-ord('0');
delete(s,1,1)
end;
t[i,j]:=k*t[i,j];
while s[1]=' ' 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]

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]

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.

I got it correct already!!!!

[arnsfelt]

Change these line
[cpp]
while (cin)
{
cin >> N;
[/cpp]

to

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

[21743NX]

Thanks alot man

I understand my problem already

it is with the EOF that loops my problem once more time berfore quiting.

Thank you.....