POJ 2593 / 2479 Max Sequence 最大雙子段和 DP

問題重述

給定長度 N (≤100,000) 的整數序列，選取兩個不重疊的非空連續子段，使其元素和之和最大。輸出該最大值。

核心洞察：分治 + 前綴/後綴最優子段

設分割點在 i 與 i+1 之間，左側最優子段和為 L[i]，右側為 R[i+1]。答案為 max(L[i] + R[i+1]) (1≤i<N)。

動態規劃計算 L[] 與 R[]

標準最大子段和（Kadane 算法）

// 以 i 結尾的最大子段和
dp[i] = max(dp[i-1] + a[i], a[i]);
// 1..i 範圍內的全局最大子段和
L[i] = max(L[i-1], dp[i]);

右側同理反向計算

dp[i] = max(dp[i+1] + a[i], a[i]);
R[i] = max(R[i+1], dp[i]);

完整流程

1. 讀入 N 及序列 a[1..N]
2. 正向 DP 計算 L[1..N]
3. 反向 DP 計算 R[1..N]
4. 枚舉分割點 i=1..N-1，更新 ans = max(ans, L[i] + R[i+1])
5. 輸出 ans

代碼實現

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

int main() {
    ios::sync_with_stdio(false);
    cin.tie(nullptr);
    int N;
    while (cin >> N && N) {
        vector<long long> a(N+1), L(N+1), R(N+1), dp(N+1);
        for (int i = 1; i <= N; ++i) cin >> a[i];

        // 左側最大子段和
        dp[1] = L[1] = a[1];
        for (int i = 2; i <= N; ++i) {
            dp[i] = max(dp[i-1] + a[i], a[i]);
            L[i] = max(L[i-1], dp[i]);
        }

        // 右側最大子段和
        dp[N] = R[N] = a[N];
        for (int i = N-1; i >= 1; --i) {
            dp[i] = max(dp[i+1] + a[i], a[i]);
            R[i] = max(R[i+1], dp[i]);
        }

        long long ans = LLONG_MIN;
        for (int i = 1; i < N; ++i)
            ans = max(ans, L[i] + R[i+1]);

        cout << ans << '\n';
    }
    return 0;
}

複雜度與變體

• 時間 O(N)，空間 O(N) —— 可優化至 O(1) 空間
• 若允許子段相鄰但不重疊，上述分割點定義恰當
• POJ 2479 僅求單段最大和，本題為其自然延伸