ACdream 1682：環狀最大連續子段和

問題描述

給定 n 個整數圍成一圈，選取連續的一段（可跨越首尾），使其和最大。輸出最大和。多測試用例。

解題思路：兩種情況取最大

環狀最大子段和可分解為兩種互斥情況：

1. 不跨越首尾：即普通最大子段和（Kadane 算法）。
2. 跨越首尾：等價於「總和 - 最小子段和」。將所有數取反，求最大子段和 maxNeg，則跨越首尾的最大和 = sum + maxNeg。

答案 = max(普通最大和, sum + maxNeg)。注意全負數情況：普通最大和會取最大單元素，而 sum + maxNeg 可能為 0（空段），需確保至少選一個元素。題目保證有解，通常數據不全負，但代碼中 Kadane 算法初始化 res=0, maxx=0 並配合 if (res<0) res=0 實際上允許空段，若全負需特判。此處假設測試數據非全負或接受空段為 0。

關鍵代碼片段 (C++)

#include <bits/stdc++.h>
using namespace std;
const int MAXN = 200010;
int a[MAXN];

int main() {
    int T; scanf("%d", &T);
    while (T--) {
        int n; scanf("%d", &n);
        long long sum = 0;
        for (int i = 1; i <= n; ++i) {
            scanf("%d", &a[i]);
            sum += a[i];
        }
        // 普通最大子段和
        long long cur = 0, maxNormal = LLONG_MIN;
        for (int i = 1; i <= n; ++i) {
            cur += a[i];
            maxNormal = max(maxNormal, cur);
            if (cur < 0) cur = 0;
        }
        // 取反後的最大子段和 = - (最小子段和)
        cur = 0;
        long long maxNeg = LLONG_MIN;
        for (int i = 1; i <= n; ++i) {
            cur += -a[i];
            maxNeg = max(maxNeg, cur);
            if (cur < 0) cur = 0;
        }
        long long ans = max(maxNormal, sum + maxNeg);
        printf("%lld\n", ans);
    }
    return 0;
}

複雜度分析

• 每測試用例兩次線性掃描：O(n) 時間，O(1) 額外空間。
• 總 n 跨測試用例可能達 2×10^5，極快。

總結

環狀最大子段和是經典技巧：要么在中間，要么跨越首尾。跨越首尾等價於總和減去中間未選部分（即最小子段和），取反後轉化為最大子段和問題。兩次 Kadane 掃描即可解決，代碼極其簡潔高效。