\(dp[i][0/1]\) 表示考虑前 \(i\) 个元素,以 \(i\) 结尾的最大子段和,\(0\) 表示还未交换过,\(1\) 表示已经交换过
\(dp[i][0] = a[i] + \max\{dp[i-1][0],0\}\)
\(dp[i][1] = \max\{dp[i][0],dp[i-1][1]+a[i],dp[i-1][0]+\max\{pre[st[i-1]-1],a[i]\},\max\{pre[i-1]\}\}\)
\(pre[i]\) 表示 \([1,i]\) 的前缀 \(\max\),\(st[i]\) 表示以 \(i\) 结尾的未交换的最大子段和的左端点。
把数组翻转一下再做一遍即可
#include <bits/stdc++.h>
#define ll long long
const int N = 5e4 + 7;
const int INF = 0x3f3f3f3f;
int a[N], st[N], n;
ll dp[N][2];
struct Bit {
int tree[N];
void clear() { memset(tree, 0, sizeof(tree)); }
void add(int x, int v) { tree[x] = v; tree[x] = std::max(tree[x], tree[x - 1]); }
int query(int x) { return tree[x]; }
} bit;
int main() {
scanf("%d", &n);
for (int i = 1; i <= n; i++)
scanf("%d", a + i), bit.add(i, a[i]);
ll ans = 0;
dp[1][0] = dp[1][1] = a[1];
st[1] = 1;
ans = std::max(1LL * a[1], ans);
for (int i = 2; i <= n; i++) {
dp[i][0] = a[i] + std::max(0LL, dp[i - 1][0]);
st[i] = i;
if (dp[i - 1][0] > 0)
st[i] = st[i - 1];
dp[i][1] = std::max(dp[i][0], dp[i - 1][1] + a[i]);
dp[i][1] = std::max(dp[i][1], dp[i - 1][0] + std::max(a[i], bit.query(st[i - 1] - 1)));
dp[i][1] = std::max(dp[i][1], 1LL * std::max(a[i], bit.query(i - 1)));
ans = std::max(ans, std::max(dp[i][0], dp[i][1]));
}
std::reverse(a + 1, a + 1 + n);
bit.clear();
for (int i = 1; i <= n; i++)
bit.add(i, a[i]);
memset(dp, 0, sizeof(dp));
memset(st, 0, sizeof(st));
dp[1][0] = dp[1][1] = a[1];
st[1] = 1;
ans = std::max(1LL * a[1], ans);
for (int i = 2; i <= n; i++) {
dp[i][0] = a[i] + std::max(0LL, dp[i - 1][0]);
st[i] = i;
if (dp[i - 1][0] > 0)
st[i] = st[i - 1];
dp[i][1] = std::max(dp[i][0], dp[i - 1][1] + a[i]);
dp[i][1] = std::max(dp[i][1], dp[i - 1][0] + std::max(a[i], bit.query(st[i - 1] - 1)));
dp[i][1] = std::max(dp[i][1], 1LL * std::max(a[i], bit.query(i - 1)));
ans = std::max(ans, std::max(dp[i][0], dp[i][1]));
}
printf("%lld\n", ans);
}