# SPOJ Aliens in a Train

I need to find the largest interval with a value less than a limit Lt.

The data is as follows:

For every test case T:

• Number of elements N, limit Lt
• N number of elements data

I wrote the following algorithm:

• Create a CF Table while taking input
• While size of interval plus current_Pos < number of elements, increase the size of interval while interval value less than limit, else increase the current_Pos

#include <iostream>
typedef long long int ll;
using namespace std;
ll a[1000000+100]={0};
int main() {
ll t;
cin>>t;
while(t--)
{
ll n,lt;
cin>>n>>lt;
for(ll i=0;i<n;i++)
cin>>a[i],a[i]+=a[i-1];
ll i=0,size=0,ans=0;
while(i+size<n)
{
while(a[i+size]-a[i-1]<=lt && i+size<n){ans=a[i+size]-a[i-1];size++;
}
i++;
}
cout<<ans<<" "<<size<<endl;
}
return 0;
}


While a similar strategy here which increases the interval and shifts it by adding the next element and removing the previous one works:

#include <iostream>
#include <cstdio>
using namespace std;
int a[100006];
int main()
{
int s,p,q,ans1,ans2,i,j,n,m,k,t,b,c,d;
scanf("%d",&t);
for(k=1;k<=t;k++)
{
scanf("%d%d",&n,&m);
for(i=1;i<=n;i++)
scanf("%d",&a[i]);
ans1=100000000;
ans2=0;
p=1;
q=1;
s=a[1];
while(q<=n && p<n)
{
if(s<=m)
{
if(q-p+1>ans2)
{
ans2=q-p+1;
ans1=s;
}
else
if(q-p+1==ans2)
ans1=min(ans1,s);
}
if(s<m)
{
q++;
s=s+a[q];
}
else
{
p++;
s=s-a[p-1];
}
}
printf("%d %d\n",ans1,ans2);
}
return 0;
}


I'd like to know where my approach fails and its actual running time.

• You're asking "where my approach fails", do you mean fails a code review and could be improved or are you not getting the results you intend? – SuperBiasedMan Nov 13 '15 at 14:10
• Fails here means failing to being bounded under O(N) ... – Siddharth Singh Nov 13 '15 at 14:11
• I am getting the desired results but it seems to exceed the time limit even though it is clearly O(N) , i don't know what am I missing in my analysis – Siddharth Singh Nov 13 '15 at 14:12
• Has there been a limit on time to comment the code, too? Consider using variable names with more than one letter. – greybeard Jan 13 '16 at 21:43