UVA 507 : Jill Rides Again

UVA507.cpp

#include <iostream>
#include <algorithm>

using namespace std;

int main()
{
  int numRoutes;
  cin >> numRoutes;
  
  for (int r=1; r<=numRoutes; r++) {
    int numStops;
    cin >> numStops;
  
    int sum_so_far = 0;
    int max_sum = 0;
    int start_edge = 1;
    
    pair<int,int> best_range = make_pair(0,0);
    for (int edge=1; edge<numStops; edge++) {
      int val;
      cin >> val;
  
      sum_so_far += val;
      if (sum_so_far < 0) {
	sum_so_far = 0;
	start_edge = edge+1;
      }

      if (sum_so_far >= max_sum) {
	if (sum_so_far == max_sum) {
	  if (best_range.first == 0) {
	    best_range = make_pair(start_edge, edge);  //initial route
	  }
	  else if (start_edge == best_range.first) {
	    best_range = make_pair(start_edge, edge);  //extending the route
	  }
	}
	else {
	  best_range = make_pair(start_edge, edge);
	}
	max_sum = sum_so_far;
      }
    }
    if (max_sum == 0) {
      cout << "Route " << r << " has no nice parts" << endl;
    }
    else {
      cout << "The nicest part of route " << r 
           << " is between stops " << best_range.first 
           << " and " << best_range.second+1 << endl;
    }
  }
  return 0;
}