108 - Maximum Sum

[new_tim]

I always got the wrong answer...
why??

[c]
#include <stdio.h>

void main()
{
int size;
int sum;
int max;
int A[101][101];
int B[101][101];

while(scanf("%d\n", &size) == 1)
{
sum = 0;
for(int i = 0; i <= 100; i++)
{
for(int j = 0; j <= 100; j++)
{
A[j] = 0;
B[j] = 0;
}
}
if(size == 0)
max = 0;
else {

for(int m = 1; m <= size; m++)
{
for(int n = 1; n <= size; n++)
{
scanf("%d", &A[m][n]);
if(m == 1 && n == 1)
max = A[m][n];
// set the initial max to the first number in the array
else if(max < A[m][n])
max = A[m][n];
// otherwise, check if each number in 1X1 square
}
}

for(int t1 = 1; t1 <= size; t1++)
{
for(int t2 = 1; t2 <= size; t2++)
{
for(int t3 = 1; t3 <= t1; t3++)
{
for(int t4 = 1; t4 <= t2; t4++)
{
B[t1][t2] = B[t1][t2]+A[t3][t4];
}
}
}
}

for(int a1 = 1; a1 <= size; a1++)
{
for(int a2 = 1; a2 <= size; a2++)
{
for(int a3 = a1; a3 <= size; a3++)
{
for(int a4 = a2; a4 <= size; a4++)
{
sum = B[a3][a4] - B[a3][a2-1] - B[a1-1][a4] + B[a1-1][a2-1];
if(max < sum)
max = sum;
}
}
}
}
printf("%d\n", max);
}
}
}
[/c]

[Ilham Kurnia]

Hi,

I'm wondering is there any algorithm faster than O(N^3) to solve 108??
I've heard rumours that O(N^2) exists, but I can't confirm it.

Cheers,

Ilham

[Dominik Michniewski]

I don't think , that exists algorithm which solve this question in O(N^2) time ... this is opinion my and people from my university ... but maybe we missed something

Cheers
Dominik

[Dominik Michniewski]

I don't think , that exists algorithm which solve this question in O(N^2) time ... this is opinion my and people from my university ... but maybe we missed something

Cheers
Dominik

[mag]

Is there multiple input in 108?

I've seen some solutions on this board using multiple input and some solutions that doesn't use multiple input....

[eric30]

Hello,

I'm so confused with that I have got so many times "Compile Error".
I hope that someone could help me find where's my problem.
Followings are my Error Message(problem 108):

/usr/lib/crt1.o: In function `_start':
/usr/lib/crt1.o(.text+0x18): undefined reference to `main'
collect2: ld returned 1 exit status

[Balon]

The input consists of an NxN array of integers

so, there is only one case in one input, not multiple.

[Boffin]

Hello, All.
I posted problem 108 and it was accepted.
But I got a letter with:

"Warning: Your program would get a Presentation Error in a true contest.
The 24-hours judge interpretes it as an "Accepted" problem."

I print my answer:
[c]printf("%d",maxSum);[/c]
What's wrong?
Should I print
[c]printf("%d\n",maxSum);[/c]
and why?

What "Presentation Error" means?

[passwd]

hi,

I'm getting Time Limit Exceeded, and I don't know why ...
If someone knows, please, advice !

Code: Select all

[c]
#include <stdio.h>
/*#define DEBUG*/

int main() {

  int n;
  int i,j;

  scanf("%d", &n);

  {
     int v[n][n];
     int k=0,m=0,maxsum=-1,aux=0,p,q;
     if(n==0) { printf("0\n"); exit(0); };
	 for(i=0;i<n;i++) for(j=0;j<n;j++) scanf("%d",&v[i][j]);

     if(n==1) {
       printf("%d\n",v[0][0]);
       return 0;
     }

     #ifdef DEBUG
         printf("\n");
    	 for(i=0;i<n;i++) {
		   for(j=0;j<n;j++) printf("%d  ",v[i][j]);
		   printf("\n");
    	 }
         printf("\n");
	 #endif

     for(i=0;i<n-1;i++) {
       for(j=i+1;j<n;j++) {
         for(k=0;k<n-1;k++) {
           for(m=k+1;m<n;m++) {
             /*calcula a soma do retangulo*/
             for(p=i;p<=j;p++) {
               for(q=k;q<=m;q++) aux+=v[p][q];
             }
             if(aux>maxsum) maxsum=aux;
             aux=0;
           }
         }
       }
     }

     printf("%d\n",maxsum);
  }

return 0;
}
[/c]

thanks !!

[Larry]

Use Dynamic Programming

[nghiank]

test

[JTK1996]

Hi,

The innermost for-loop is run 10^6 times, I think that is too much. Dynamic Programming, as mentioned before, sounds like a good
way to reduce time consumption.

[junjieliang]

If you know how to solve the 1-d problem in O(n) time, without DP you can get O(n^4) algorithm, which (although not the best) will pass the time limit.

[peterlin]

Excuse me,
May I ask what's the algo is O(n^3) for this problem ?

Best wishes,
Peter

[peterlin]

Excuse me,
May I ask what's the algo is O(n^3) for this problem ?

Best wishes,
Peter