108 - Maximum Sum
Moderator: Board moderators
108 - what happens to a input of zeros
What should be the output to this:
3
0 0 0
0 0 0
0 0 0
Any ideas?
3
0 0 0
0 0 0
0 0 0
Any ideas?
-
- New poster
- Posts: 11
- Joined: Wed Jun 21, 2006 5:11 pm
- Contact:
Yeah It is 0
Anything other than Accepted is irritating,even Presentation Error
http://acm.uva.es/problemset/usersjudge.php?user=40301
http://acm.uva.es/problemset/usersjudge.php?user=40301
108 faster than O(N^4) but got WA
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:
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 *
Last edited by rickyliu on Fri Nov 10, 2006 9:51 am, edited 1 time in total.
Try these test cases
Both of thier answers are 12.
Best regards.
![:)](./images/smilies/icon_smile.gif)
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
Best regards.
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 *
Last edited by rickyliu on Fri Nov 10, 2006 9:52 am, edited 1 time in total.
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.
The answer is 10, but your output is 11.
Best regards.
I'll only give you critical test case.
![:)](./images/smilies/icon_smile.gif)
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
Best regards.
-
- New poster
- Posts: 21
- Joined: Sat Oct 21, 2006 11:50 pm
- Contact:
-
- Learning poster
- Posts: 63
- Joined: Tue Mar 07, 2006 6:51 pm
- Location: india
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]
#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]
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.
Ami ekhono shopno dekhi...
HomePage
HomePage
108 help meeeee
#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?
#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?
108 help meeeee
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;
}
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;
}