UVa 507 - Jill Rides Again

// UVa 507 - Jill Rides Again

#include <iostream>
#include <stdio.h>
using namespace std;

#define datatype signed long long int

int main() {
	int rr;
	cin >> rr;
	for (int r = 1; r <= rr; r++) {
		int n;
		cin >> n;
		datatype best_niceness = 0;
		int best_i = 0, sumi = 1;
		int best_j = 0;
		datatype sum = 0;
		for (int i = 1; i < n; i++) {
			datatype niceness;
			cin >> niceness;
			sum += niceness;
			if (sum > best_niceness || sum == best_niceness && i - sumi > best_j - best_i) {
				best_niceness = sum;
				best_i = sumi;
				best_j = i;
			}
			if (sum < 0) {
				sum = 0;
				sumi = i + 1;
			}
		}
		if (best_j == 0)
			printf("Route %d has no nice parts\n", r);
		else
			printf("The nicest part of route %d is between stops %d and %d\n", r, best_i, best_j + 1);
	}

	return 0;
}