Luogu P1121 环状最大两段子段和 题解 [ 绿 ] [ 分类讨论 ] [ 线性 DP ]

环状最大两段子段和

你怎么知道我只会了 DDP 断环为链的做法？？？？？？？

观察两段最大子段和的形态，发现只可能有下面两种情况：

• \(\texttt{......AAAAA.....BBBBBB....}\)。
• \(\texttt{AAAAA.....BBBBBB....AAAAAA}\)。

第一种情况是好做的，直接求前后缀的非空最大子段和，枚举中间的分割点即可。

考虑第二种。发现直接 DP 并不好做，因为有三段被选中。但是我们注意到不被选的部分只有两段。于是我们对这两段求一个最小子段和即可，用总和减去两段的最小子段和即为答案。

注意求最小子段和的时候，两侧不能选完整个序列。因此我们可以拆成两部分计算贡献：

• \([2, l], [r, n - 1]\) 的贡献，在这里面选一定不会把整个序列选中。
• \([1, l - 1], [r + 1, n]\) 的贡献，\(l - 1, r + 1\) 是因为必须保证不选中整个序列。

时间复杂度 \(O(n)\)。

#include <bits/stdc++.h>
#define fi first
#define se second
#define eb(x) emplace_back(x)
#define pb(x) push_back(x)
#define lc(x) (tr[x].ls)
#define rc(x) (tr[x].rs)
using namespace std;
typedef long long ll;
typedef unsigned long long ull;
typedef long double ldb;
using pi = pair<int, int>;
const int N = 200005;
const ll inf = 0x3f3f3f3f3f3f3f3f;
ll n, a[N], f[N], g[N], ans = -inf, sm = 0;
int main()
{//freopen("sample.in", "r", stdin);//freopen("sample.out", "w", stdout);ios::sync_with_stdio(0);cin.tie(0);cout.tie(0);cin >> n;ll pre = 0;for(int i = 1; i <= n; i++){cin >> a[i];sm += a[i];}    for(int i = 2; i <= n; i++){pre = a[i] + min(0ll, pre);f[i] = min(f[i - 1], pre);}    pre = 0;for(int i = n - 1; i >= 1; i--){pre = a[i] + min(0ll, pre);g[i] = min(g[i + 1], pre);}pre = 0;for(int i = 1; i <= n; i++){f[i] = min(f[i], min(f[i - 1], pre));pre += a[i];}pre = 0;for(int i = n; i >= 1; i--){g[i] = min(g[i], min(g[i + 1], pre));pre += a[i];}    for(int i = 1; i < n; i++) ans = max(ans, sm - f[i] - g[i + 1]);pre = 0;f[0] = -inf;for(int i = 1; i <= n; i++){pre = a[i] + max(0ll, pre);f[i] = max(f[i - 1], pre);}      pre = 0;g[n + 1] = -inf;for(int i = n; i >= 1; i--){pre = a[i] + max(0ll, pre);g[i] = max(g[i + 1], pre);}          for(int i = 1; i < n; i++) ans = max(ans, f[i] + g[i + 1]);cout << ans;return 0;
}