就是最大子段和的变体。最大子段和只要一个数组，记录前i个里的最大子段和在f[i]里就行了，但是最大子段积因为有负乘负得正这一点，所以还需要把前i个里的最小子段积存起来。就可以了。直接上代码：
/* * Author : ben */ #include <cstdio> #include <cstdlib> #include <cstring> #include <cmath> #include <ctime> #include <iostream> #include <algorithm> #include <queue> #include <set> #include <map> #include <stack> #include <string> #include <vector> #include <deque> #include <list> #include <functional> #include <numeric> #include <cctype> using namespace std; //输入非负整数，用法int a = get_int(); int get_int() { int res = 0, ch; while (!((ch = getchar()) >= '0' && ch <= '9')) { if (ch == EOF) return -1; } res = ch - '0'; while ((ch = getchar()) >= '0' && ch <= '9') res = res * 10 + (ch - '0'); return res; } //输入整数(包括负整数，故不能通过返回值判断是否输入到EOF，本函数当输入到EOF时，返回-1)，用法int a = get_int2(); int get_int2() { int res = 0, ch, flag = 0; while (!((ch = getchar()) >= '0' && ch <= '9')) { if (ch == '-') flag = 1; if (ch == EOF) return -1; } res = ch - '0'; while ((ch = getchar()) >= '0' && ch <= '9') res = res * 10 + (ch - '0'); if (flag == 1) res = -res; return res; } const int MAXN = 10009; int maxr[MAXN], minr[MAXN]; inline int mymul(int a, int b) { int sign = 1; if (a * b == 0) { return 0; } if (a * b < 0) { sign = -1; } return sign * (abs(a) + abs(b)); } int main() { int T = get_int(), tmp, N; int a[3]; for (int t = 1; t <= T; t++) { N = get_int(); maxr[0] = minr[0] = 0; int ans = 0; for (int i = 1; i <= N; i++) { tmp = get_int2() / 2; a[0] = mymul(maxr[i - 1], tmp); a[1] = mymul(minr[i - 1], tmp); a[2] = tmp; sort(a, a + 3); maxr[i] = a[2]; ans = maxr[i] > ans ? maxr[i] : ans; minr[i] = a[0]; } printf("Case #%d: %d ", t, ans); } return 0; }