Input:::
Code: Select all
1
5
3
-3
4
1
Code: Select all
The nicest part of route 1 is between stops 1 and 5
Moderator: Board moderators
Code: Select all
1
5
3
-3
4
1
Code: Select all
The nicest part of route 1 is between stops 1 and 5
Maximum sum of a consecutive sequence.shahriar717 wrote:will anyone tell me the algo for this problem??
i am distressed about this........
Code: Select all
#include<iostream>
#include<cstdio>
#include<stdlib.h>
using namespace std;
#define S 99999
struct lar
{
int lar;
int a,b;
}st[99999];
int main()
{
int num[S], sum[S];
int i,j,k;
int n;
int t;
cin >> t;
for(k=1; k<=t; k++)
{
cin >> n;
if(n==0)
{cout <<"Route "<<k<<" has no nice parts\n";continue;}
n--;
int m;
for(i=0; i<n; i++)
cin >> num[i];
m=sum[0]=num[0];
int x,y;
int largest=0;
int l=0;
x=y=0;
for(i=1; i<n; i++)
{
sum[i]=num[i]+sum[i-1];
if(sum[i]<num[i])
{
st[l].lar=y-x;
st[l].a=x;
st[l].b=y; l++;
x=y=i;
sum[i]=max(sum[i],num[i]);
}
if(sum[i]>=m)
{
y=i;
}
m=max(m,sum[i]);
}
for(i=0; i<l; i++)
{
if(st[i].lar>largest)
{
x=st[i].a;
y=st[i].b;
}
}
if(m>0)
cout << "The nicest part of route "<<k<<" is between stops "<< x+1 <<" and " <<y+1+1 <<endl;
else
cout <<"Route "<<k<<" has no nice parts\n";
}
return 0;
}
Code: Select all
#include <iostream>
#include <sstream>
#include <vector>
#include <cstdio>
using namespace std;
struct route
{
int start;
int last;
};
int main()
{
int n;
scanf("%d",&n);
int m,l;
int sum=0;
int max_sum=0;
for(int loop=1;loop<=n;loop++)
{
struct route temp;
scanf("%d",&m);
temp.start=m-2;
max_sum=0;
sum=0;
int a[m-1];
for(int i=0;i<m-1;i++)
scanf("%d",&a[i]);
for(int i=m-2;i>=0;i--)
{
//scanf("%d",&l);
l=a[i];
sum+=l;
if(sum<0)
{
sum=0;
temp.start=i-1;
}
else if(sum>=0&&max_sum<=sum)
{
max_sum=sum;
//printf("ksdj");
temp.last=i;
//cout<<sum<<" "<<max_sum<<" "<<temp.start<<" "<<temp.last<<endl;
}
//cout<<sum<<" "<<max_sum<<" "<<temp.start<<" "<<temp.last<<endl;
}
if(max_sum==0)
{
//cout<<max_sum<<endl;
cout<<"Route "<<loop<<" has no nice parts"<<endl;
}
else
{
cout<<"The nicest part of route "<<loop<<" is between stops "<<temp.last+1<<" and "<<temp.start+2<<endl;
}
}
return 0;
}
check the below input:shankhs wrote:Help
Code: Select all
1
11
1
1
1
-100
2
2
-100
1
1
1
Code: Select all
The nicest part of route 1 is between stops 5 and 7
Code: Select all
The nicest part of route 1 is between stops 5 and 4
shankhs wrote:Thanx Mak
I got AC in 0.124 secs but I see many people getting AC in 0.000 sec!
What optimization could be done here?
It definitely fits in an int.sazzadcsedu wrote:Can someone post me some I/O of this problem?? My program passed all the test case from the previous post. But still
WA. Plz someone help. Is int data type is enough for this problem???
Code: Select all
Code: Select all
1
7
1
2
3
-34
3
3