本文共 1049 字，大约阅读时间需要 3 分钟。
求一个区间内连续两段不相交区间最大和。
// File Name: 2479.cpp// Author: Missa_Chen// Created Time: 2013年06月22日 星期六 16时19分02秒#include #include #include #include #include #include #include #include #include #include #include using namespace std;#define LL long longconst int inf = 0x3f3f3f3f;const int maxn = 5e4 + 5;int n;int num[maxn], st[maxn], end[maxn];int main(){ int cas; scanf("%d", &cas); while (cas --) { scanf("%d", &n); for (int i = 1; i <= n; ++i) scanf("%d", &num[i]); for (int i = 0; i <= n + 1; ++i) st[i] = end[i] = -inf; int tmp = -inf, ans = -inf; for (int i = 1; i <= n; ++i) { if (tmp >= 0) tmp += num[i]; else tmp = num[i]; end[i] = max(end[i - 1], tmp); } tmp = -inf; for (int i = n; i >= 1; --i) { if (tmp >= 0) tmp += num[i]; else tmp = num[i]; st[i] = max(st[i + 1], tmp); } for (int i = 1; i < n; ++i) ans = max(ans, end[i] + st[i + 1]); printf("%d\n", ans); } return 0;}
转载于:https://www.cnblogs.com/Missa/p/3149888.html