题目大意：最大和子序列问题。由于具有最大和的子序列具有一下性质：第一项不为负数，并且从第一项开始累加，中间不会有和出现负数，因为一旦有负数我们可以抛弃前边的部分以得到更大的子序列和，这将会产生矛盾。
1 #include <cstdio> 2 3 int main() 4 { 5 #ifdef LOCAL 6 freopen("in", "r", stdin); 7 #endif 8 int T; 9 scanf("%d", &T); 10 for (int kase = 1; kase <= T; kase++) 11 { 12 int n; 13 scanf("%d", &n); 14 int x, sum = 0, nicest = 0, len = 0; 15 int p = 0, s, e; 16 for (int i = 0; i < n-1; i++) 17 { 18 scanf("%d", &x); 19 sum += x; 20 if (sum < 0) 21 { 22 sum = 0; 23 p = i + 1; 24 } 25 else if (sum > nicest || (sum == nicest && i-p+1 > len)) 26 { 27 s = p; 28 e = i; 29 len = i - p + 1; 30 nicest = sum; 31 } 32 } 33 if (nicest > 0) printf("The nicest part of route %d is between stops %d and %d ", kase, s+1, e+2); 34 else printf("Route %d has no nice parts ", kase); 35 } 36 return 0; 37 }