最大連續子序列和 (HDU 1003) 五種解法總結

問題

給定序列 a[1..n] (n≤100000)，求最大子段和及其起始、結束位置 (多解取起點最小、再取終點最小)。T≤20 組測試。

方法對比

掃描法核心邏輯

int maxSum = -INF, curSum = 0;
int start = 1, end = 1, tempStart = 1;
for (int i = 1; i <= n; ++i) {
    curSum += a[i];
    if (curSum > maxSum) {
        maxSum = curSum;
        start = tempStart;
        end = i;
    }
    if (curSum < 0) {
        curSum = 0;
        tempStart = i + 1;
    }
}

完整代碼 (C++)

#include <bits/stdc++.h>
using namespace std;
const int INF = 1e9;
int a[100010];

int main() {
    ios::sync_with_stdio(false);
    cin.tie(nullptr);
    int T; cin >> T;
    for (int cs = 1; cs <= T; ++cs) {
        int n; cin >> n;
        for (int i = 1; i <= n; ++i) cin >> a[i];
        int maxSum = -INF, curSum = 0;
        int L = 1, R = 1, tmpL = 1;
        for (int i = 1; i <= n; ++i) {
            curSum += a[i];
            if (curSum > maxSum) {
                maxSum = curSum; L = tmpL; R = i;
            }
            if (curSum < 0) { curSum = 0; tmpL = i + 1; }
        }
        cout << "Case " << cs << ":\n" << maxSum << ' ' << L << ' ' << R << "\n";
        if (cs != T) cout << "\n";
    }
    return 0;
}

分治法思想 (補充)

遞歸求左半、右半、跨中間最大子段和。跨中間從中點向左右擴展維護最大前綴/後綴和。結構體保存 {值, 左, 右} 便於合併。

線段樹節點信息

每節點維護：區間和、最大前綴和/位置、最大後綴和/位置、最大子段和/位置。合併操作利用結合律，查詢整個區間即得答案。