Advertisement
Not a member of Pastebin yet?
Sign Up,
it unlocks many cool features!
- #include<iostream>
- #include<climits>
- using namespace std;
- int max_subarray_sum(int a[],int n,int test)
- {
- int sum=0,maxsum=INT_MIN, start =0, end = 0, s=0; ;
- for(int i=0;i<n;i++)
- {
- sum=sum+a[i];
- if(sum>=maxsum)
- {
- if(sum>maxsum || (sum==maxsum && i-s>end-start))
- {
- start = s;
- end = i;
- }
- maxsum=sum;
- }
- if(sum<0)
- {
- sum=0;
- s = i + 1;
- }
- }
- if(maxsum>0)
- {
- cout<<"The nicest part of route "<<test<<" is between stops "<<start+1<<" and "<<end+2<<endl;
- }
- else
- cout<<"Route "<<test<<" has no nice parts"<<endl;
- }
- int main()
- {
- int test;
- cin>>test;
- for(int t=1;t<=test;t++)
- {
- int stops;
- cin>>stops;
- int arr[stops],maxsum;
- for(int i=0;i<stops-1;i++)
- {
- cin>>arr[i];
- }
- max_subarray_sum(arr,stops-1,test);
- }
- return 0;
- }
Advertisement
Add Comment
Please, Sign In to add comment
Advertisement