文字教学

这道题用前后缀预处理+枚举分割点解决，核心思路是将数组拆分为左右两部分，分别预处理最大子段和后再组合：

1. 预处理前缀最大子段和：用 l[i] 表示以第 i 个元素结尾的最大子段和，lm[i] 表示前 i 个元素中的最大子段和。
2. 预处理后缀最大子段和：用 r[i] 表示以第 i 个元素开头的最大子段和，rm[i] 表示从 i 到末尾的最大子段和。
3. 枚举分割点：遍历所有可能的间隔位置 k，计算 lm[k] + rm[k+2]（保证两个子段至少间隔一个数），取最大值即为答案。

代码

#include <bits/stdc++.h>
using namespace std;

typedef long long ll;
const int N = 1e6 + 10;
ll a[N], l[N], lm[N], r[N], rm[N];

int main() {
    int n, i;
    ll ans = -1e18;
    scanf("%d", &n);
    for (i = 0; i < n; ++i) scanf("%lld", &a[i]);
    
    // 预处理前缀
    l[0] = a[0];
    lm[0] = a[0];
    for (i = 1; i < n; ++i) {
        l[i] = max(a[i], l[i-1] + a[i]);
        lm[i] = max(lm[i-1], l[i]);
    }
    
    // 预处理后缀
    r[n-1] = a[n-1];
    rm[n-1] = a[n-1];
    for (i = n-2; i >= 0; --i) {
        r[i] = max(a[i], r[i+1] + a[i]);
        rm[i] = max(rm[i+1], r[i]);
    }
    
    // 枚举分割点
    for (i = 0; i <= n-3; ++i) {
        ans = max(ans, lm[i] + rm[i+2]);
    }
    printf("%lld\n", ans);
    return 0;
}