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;}