Question : spoj.pl/problems/GSS1/
First , it was giving TLE in 9th test case when scanf is used .
After changing scanf to getchar , it's giving wrong answer . And also , Confirm me please that whether should I give the -ve ans or zero for [color=#000080]-ve array[/color] ?
I've tried for both cases but still showing wrong ans .
Complexity is O(n) .
#include<stdio.h>
#include<stdlib.h>
#define max(x,y) (x>y?x:y)
int main()
{
long t=0,i=0,m=0,c,q=0;
while((c=getchar())!='\n')
t=t*10+c-'0';
long an[t];
for(i=0;i<t;i++)
an[i]=0;
i=0;
while(i<t)
{
c=getchar();
if(c=='\n') break;
if(c=='-')
q=1;
else if(c==' ')
{
if(q) an[i]*=-1;
q=0;i++;
}
else an[i]=an[i]*10+c-'0';
}
if(q) an[i]*=-1;
while((c=getchar())!='\n')
m=m*10+c-'0';
while(m--)
{
long a=0,b=0,k=2,p=0;
long s=0L;c=0;
while((c=getchar())!=' ')
{
a=a*10+c-'0';
}
while((c=getchar())!='\n')
{
b=b*10+c-'0';
}
long s1=0,n=0, min=an[a-1];
for(i=a-1;i<b;i++)
{ if(an[i]<0)
min=(an[i]>min)?an[i]:min;
else { n=1;break;}
}
if(!n) s1=min; // If all nums are -ve , then s1 =0 (if want to ) else s1=min (means min(-ve))
else
for(i=a-1;i<b;i++)
{
s+=an[i];
if(s<0)
s=0;
else if(s1<s)
s1=s;
}
printf("%ld\n",s1);
}
return 0;
}