## 108 - Maximum Sum

Moderator: Board moderators

brianfry713
Guru
Posts: 5947
Joined: Thu Sep 01, 2011 9:09 am
Location: San Jose, CA, USA

### Re: 108-Maximum Sum WA

Check input and AC output for thousands of problems on uDebug!

richard1017
New poster
Posts: 3
Joined: Mon Jan 20, 2014 2:38 am

### 108 - Maximum Sum - WA

I test my code on several arrays and got the correct answer. However, the verdict says a WA.
Could you please check my code?
Thank you.

Code removed after AC.
Last edited by richard1017 on Wed Jan 22, 2014 1:33 am, edited 1 time in total.

brianfry713
Guru
Posts: 5947
Joined: Thu Sep 01, 2011 9:09 am
Location: San Jose, CA, USA

### Re: 108 - Maximum Sum - WA

Print a newline char at the end of the line.
Check input and AC output for thousands of problems on uDebug!

richard1017
New poster
Posts: 3
Joined: Mon Jan 20, 2014 2:38 am

### Re: 108 - Maximum Sum - WA

brianfry713 wrote:Print a newline char at the end of the line.
Thanks, Accepted!

vilash99
New poster
Posts: 2
Joined: Wed Nov 07, 2012 11:44 pm

I used following code. Work fine for given input and my various test inputs. But WA
My code:

Removed after AC.
Last edited by vilash99 on Fri Feb 14, 2014 6:39 pm, edited 1 time in total.

brianfry713
Guru
Posts: 5947
Joined: Thu Sep 01, 2011 9:09 am
Location: San Jose, CA, USA

### Re: 108 - Wrong answer

What is your algorithm? You can solve this in O(N ^ 5)
Check input and AC output for thousands of problems on uDebug!

vilash99
New poster
Posts: 2
Joined: Wed Nov 07, 2012 11:44 pm

### Re: 108 - Wrong answer

Thanks, for suggestion.
I was trying to get O(N ^ 4) using Kadane algorithms.
Got AC in O(N^5)

cunbidun
New poster
Posts: 3
Joined: Fri Oct 23, 2015 6:35 am

### Re: 108 - Maximum Sum

my code work fine with random test but when i submit still WA
my code:

Code: Select all

``````#include<stdio.h>
#include<string.h>
int maxx(int a,int b){
if(a>b) return a;
else return b;
}

int main(){
freopen("tongcn1.inp","r",stdin);
//freopen("tongcn1.out","w",stdout);
int n,a[125][127],i,j,s[127][127],max[127][127],maxt,k,ma,l   ;
scanf("%d",&n);
for(i=0;i<=n;i++)
s[i][0]=0;
for(j=0;j<=n;j++)
s[0][j]=0;
for(i=1;i<=n;i++)
{
for(j=1;j<=n;j++)
{
scanf("%d",&a[i][j]);
s[i][j]=s[i-1][j]+s[i][j-1]-s[i-1][j-1]+a[i][j];
}
}
maxt=a[1][1];

for(i=1;i<=n;i++)
for(j=1;j<=n;j++)
{
for(l=0;l<i;l++)
for(k=0;k<j;k++)
{

ma=s[i][j]-s[l][j]-s[i][k]+s[l][k];

if(ma>maxt) maxt=ma;
}

}
printf("%d",maxt);
}``````