HDU Max Sum：最大子段和 DP 掃描法（Kadane 算法）

問題描述

給定數組，求連續子數組的最大和，並輸出該子段的起始、結束索引（1-based）。多測試用例。

Kadane 算法核心思想

掃描維護 dp[i] = 以 i 結尾的最大子段和：

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

若 dp[i-1] < 0，拋棄前綴，從 a[i] 重新開始。同時記錄全局最大值及其區間。

完整代碼

#include <cstdio>
#include <cstring>
#include <algorithm>
using namespace std;

const int MAXN = 100005;
int a[MAXN];

int main() {
    int T; scanf("%d", &T);
    for (int tc=1; tc<=T; ++tc) {
        int n; scanf("%d", &n);
        for (int i=1; i<=n; ++i) scanf("%d", &a[i]);
        int best = -1e9, cur = 0;
        int L=1, R=1, curL=1;
        for (int i=1; i<=n; ++i) {
            if (cur < 0) { cur = a[i]; curL = i; }
            else cur += a[i];
            if (cur > best) { best = cur; L = curL; R = i; }
        }
        printf("Case %d:\n%d %d %d\n\n", tc, best, L, R);
    }
    return 0;
}

關鍵點

• 單次掃描 O(n) 時間，O(1) 空間
• 區間記錄：curL 標記當前子段起點，更新全局最優時同步 L,R
• 全負數組時正確選取最大元素（長度 1）

複雜度

• 時間：O(n) 每測試用例
• 空間：O(1)