uva - 507 Jill Rides Again Solution

Algorithm : Kadane Algo.

#include<iostream>
#include<vector>

using namespace std;

void kasane_algo(int *arr,int n,int &start_index,int &end_index){
int temp,i,diff,max;
temp=max=arr[0];
start_index=0;
vector<int> vec;
if(temp>0){
vec.push_back(1);
vec.push_back(2);
}
for(i=1;i<n;i++){
if(temp<0){
start_index=i;
temp=0;
}
if(max<0 && arr[i]<0){
temp=-1;
}else{
temp=temp+arr[i];
if(temp>=max){
if(temp>max){
vec.clear();
max=temp;
}
vec.push_back(start_index+1);
vec.push_back(i+2);
}
}
}
diff=0;
max=vec.size();
for(i=0;i<max;i=i+2){
if((vec[i+1]-vec[i])>diff){
diff=vec[i+1]-vec[i];
start_index=vec[i];
end_index=vec[i+1];
}
}
}

int main(){
int arr[20001],i,kase,start_index,end_index,test_case,n;
bool flag;
cin>>kase;
test_case=1;
while(kase>=test_case){
cin>>n;
flag=true;
for(i=0;i<n-1;i++){
cin>>arr[i];
if(arr[i]>0)
flag=false;
}
if(flag){
cout<<"Route "<<test_case<<" has no nice parts"<<endl;
}else{
kasane_algo(arr,n-1,start_index,end_index);
cout<<"The nicest part of route "<<test_case<<" is between stops "<<start_index<<" and "<<end_index<<endl;
}
test_case++;
}
return 0;
}