UVA 507 Jill Rides Again 最大子序列和
很裸的最大子序列和。
具体算法分析见六种姿势拿下连续子序列最大和问题。
代码：
/* * Author: illuz <iilluzen[at]gmail.com> * Blog: http://blog.csdn.net/hcbbt * File: uva507.cpp * Lauguage: C/C++ * Create Date: 2013-09-05 00:09:13 * Descripton: UVA 507 Jill Rides Again */#include <cstdio>#define rep(i, n) for (int i = 0; i < (n); i++)const int MAXN = 20010;int a[MAXN];void maxSeq(int* a, int len, int &res, int &l, int &r) {res = a[0], l = 0, r = len - 1;int sum = 0, tl = 0;for (int i = 0; i < len; i++) {if (sum < 0) {sum = a[i];tl = i;}else sum += a[i];if (res < sum || (res == sum && l == tl)) res = sum, l = tl, r = i;}}int main() {int n, t;scanf("%d", &t);rep(cas, t) {scanf("%d", &n);n--;rep(i, n) scanf("%d", &a[i]);int l, r, res;maxSeq(a, n, res, l, r);if (res <= 0) printf("Route %d has no nice parts\n", cas + 1);else printf("The nicest part of route %d is between stops %d and %d\n", cas + 1, l + 1, r + 2);}return 0;}