108 - Maximum Sum

[ahmad_h]

What should be the output to this:
3
0 0 0
0 0 0
0 0 0

Any ideas?

[mahan]

it should be 0..

[pankaj trivedi]

Yeah It is 0

[rickyliu]

I have tried all the test inputs in this board and got the correct answers
but I got WA from the judge. Would anyone please provide more testing
cases or tell me what's wrong in my code:

Code: Select all

* code removed *

[tan_Yui]

Try these test cases

Code: Select all

4
0  0  0  0
1  1 -4  3
1  2 -5  4
1  3 -6  5

Code: Select all

4
0  1  1  1
0  1  2  3
0 -4 -5 -6
0  3  4  5

Both of thier answers are 12.

Best regards.

[rickyliu]

Thank you for the test cases. I found my bugs. Now, my code shows 12 correctly for these cases. However, I still got WA. I am stuck. Any help, please. Here is my new code:

Code: Select all

* code removed *

[tan_Yui]

I think the cause of WA is the little bugs in your code, but I can't analyze because I'm not good at C++.
I'll only give you critical test case.

Code: Select all

5
-3 -2 -1  0  1
-2 -1  0  1  2
-1  0  1  2  3
 0  1  2  3 -4
 1  2  3 -4 -5

The answer is 10, but your output is 11.

Best regards.

[rickyliu]

Thank you! You are very helpful. I finally got AC.

It runs (0.752) only slightly faster than the O(N^4) algorithm (0.891) previously accpeted. My ranking is 3,000+. I am wondering how those people ran so fast.

[yoshiro aoki]

-1, as no larger is possible from the matrix.

maybe coffee will help?

[mukeshtiwari]

thnkx for ur algorithm but one thing i did not under how it is ossible to solve this problem in 000 sec .explain me...i m giving my code here plz tell how it can be improved further to get time limit 0 sec....
#include<stdio.h>
#define INFINITY -99999
int sum[110];
void initial()
{
int i;
for(i=0;i<110;i++)
sum[i]=0;
}

int kadan(int* arr,int n)
{
int i,a,b,aa,bb,curr,max;
//scanf("%d",&n);
//for(i=0;i<n;i++)
//scanf("%d",&arr[i]);
max=INFINITY;
a=0;
b=0;
curr=0;
aa=0;
for(bb=0;bb<n;bb++)
{
curr=curr+arr[bb];
if(curr>max)
{
max=curr;
a=aa;
b=bb;
}
if(curr<0)
{
curr=0;
aa=bb+1;
}
}
//printf("max in function call %d\n",max);

return(max);

}
main()
{

int n,i,j,a[110][110],k,v,max;

scanf("%d",&n);
for(i=0;i<n;i++)
for(j=0;j<n;j++)
scanf("%d",&a[i][j]);


for(k=0;k<n;k++)
{
initial();
{
for(i=k;i<n;i++)
{
for(j=0;j<n;j++)
{
sum[j]=sum[j]+a[i][j];
}

v=kadan(sum,n);
if(k==0)
max=v;
else if(v>max)
max=v;
//printf("max in main %d\n",max);
}
}
}

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

[b][/b][code][/code][color=red][/color][color=red][/color]

[Jan]

There is only one input, so if you somehow find the output, then just 'printf', or 'cout' would be the solution. If your timing is .02 - .05 sec, then its good.

[rezaee]

#include <iostream.h>
#include <stdio.h>

int main(void)
{int n,p,sum,max=-127;
int m[100][100];
cin>>n;
{{for(int i=0;i<n;i++)
for(int j=0;j<n;j++)
{cin>>p;m[j]=p;}

for(int i=0;i<n;i++)
for(int j=0;j<n;j++)
for(int k=0;k<n;k++)
for(int z=0;z<n;z++)

{sum=0;
for(int y=i;y<=j;y++)
for(int x=k;x<=z;x++)
sum+=m[y][x];
if(sum>max)max=sum;}

cout<<max;
}
return 0;}

time limited;what do i?

[helloneo]

there are a lot of threads on this problem..
so.. please search..!
and don't make a new thread if one already exists

[rezaee]

it is my code.

but i get a WA.

#include <iostream.h>

int n;
int b[101][101];

int main()
{
int a[101][101];
int i,j,k;
int max;
int s;
while(cin>>n)
{max=-127;
for(i=1;i<=n;i++)
{
for(j=1;j<=n;j++)
{
cin>>a[j];
if(a[j]>max)
{
max=a[j];
}
b[j]=b[i-1][j]+b[j-1]-b[i-1][j-1]+a[j];
if(b[j]>max)
{
max=b[j];
}
}
}

for(i=1;i<=n;i++)
{
for(j=1;j<=n;j++)
{
for(k=1;k<=n;k++)
{
if(k<j)
{
temp=b[j]-b[k];
if(s>max) max=s;
}
if(k<i)
{
s=b[i][j]-b[k][j];
if(s>max) max=s;
}
if(k<i && k<j)
{
s=b[i][j]-b[k][j]-b[i][k]+b[k][k];
if(s>max) max=s;
}
}
}
}
cout<<max<<endl;}
return 0;
}

[huan086]

I believe this line is wrong

temp=b[j]-b[k];
if(s>max) max=s;

i think you mean s=b...