最大双子段和(Maximum Two Subarray Sum) 题解

思路分析

从左往右用 Kadane 算法求出前缀 $[1, i]$ 内的最大非空子段和 preMax[i]，再从右往左求出后缀 $[i, n]$ 内的最大非空子段和 sufMax[i]。由于两个子段之间至少间隔一个数，枚举中间被隔开的分界位置 $k \in [2, n - 1]$，答案即为 $\max_{2 \le k \le n - 1}(\text{preMax}[k - 1] + \text{sufMax}[k + 1])$。注意全负数时子段不可为空，初值需设为极小值且用 long long。时间复杂度 $O(n)$。

参考代码

#include <algorithm>
#include <iostream>
using namespace std;

const int MX = 1000005;
long long a[MX], preMax[MX], sufMax[MX];

int main()
{
    ios::sync_with_stdio(false);
    cin.tie(nullptr);
    int n;
    if (!(cin >> n)) return 0;
    for (int i = 1; i <= n; ++i) cin >> a[i];

    long long cur = a[1];
    preMax[1] = a[1];
    for (int i = 2; i <= n; ++i)
    {
        cur = max(a[i], cur + a[i]);
        preMax[i] = max(preMax[i - 1], cur);
    }

    cur = a[n];
    sufMax[n] = a[n];
    for (int i = n - 1; i >= 1; --i)
    {
        cur = max(a[i], cur + a[i]);
        sufMax[i] = max(sufMax[i + 1], cur);
    }

    long long ans = preMax[1] + sufMax[3];
    for (int k = 2; k <= n - 1; ++k)
    {
        ans = max(ans, preMax[k - 1] + sufMax[k + 1]);
    }
    cout << ans << "\n";
    return 0;
}