HDU 1003 Max Sum 最大子陣列和：Kadane 演算法完整解析與 AC 代碼

HDU 1003 Max Sum 最大子陣列和：Kadane 演算法完整解析與 AC 代碼

題目連結：HDU 1003

核心任務：給定整數序列，找出連續子陣列使其和最大，輸出最大和、起始位置、結束位置（1-based 索引）。多測資格式。

一、演算法核心：Kadane 算法 O(N) 單掃描

維護兩個變數：

• current_sum：以當前元素結尾的最大子陣列和
• max_sum：全域最大和

關鍵邏輯：

current_sum += a[i];
if (current_sum > max_sum) {
    max_sum = current_sum;
    // 更新起終點
}
if (current_sum < 0) {
    current_sum = 0;      // 捨棄負前綴
    temp_start = i + 1;   // 新子陣列從下一個開始
}

直觀理解：負數前綴只會拖累後續和，果斷歸零重來。正數前綴則保留延伸。

二、完整 AC 代碼（C 語言，符合 HDU 編譯環境）

#include <stdio.h>
#include <string.h>

int main() {
    int T, n;
    scanf("%d", &T);
    for (int tc = 1; tc <= T; ++tc) {
        scanf("%d", &n);
        int max_sum = -1001;  // 題目範圍 -1000~1000
        int cur_sum = 0;
        int best_l = 1, best_r = 1;
        int cur_l = 1;

        for (int i = 1; i <= n; ++i) {
            int x; scanf("%d", &x);
            cur_sum += x;
            if (cur_sum > max_sum) {
                max_sum = cur_sum;
                best_l = cur_l;
                best_r = i;
            }
            if (cur_sum < 0) {
                cur_sum = 0;
                cur_l = i + 1;
            }
        }
        printf("Case %d:\n%d %d %d\n", tc, max_sum, best_l, best_r);
        if (tc != T) printf("\n");  // 題目要求案例間空行
    }
    return 0;
}

三、關鍵細節與避坑指南

1. 全負數陣列處理：初始 max_sum 必須小於最小可能值（題目 -1000，設 -1001），確保至少選取一個元素
2. 索引 1-based：輸出位置需 +1
3. 多測資格式：案例間輸出空行，最後一案例不輸出
4. 輸入規模：n ≤ 100000，O(N) 單掃描完美通過，int 足夠（最大和 1e8）
5. 快速 IO：大量輸入建議用 scanf 或自訂快速讀取

四、變體延伸：輸出子陣列本身 / 矩陣最大子矩陣和

• 若需輸出子陣列元素，記錄 best_l, best_r 後二次遍歷印出
• 二維最大子矩陣和：固定上下行，將列壓縮為一維陣列套用 Kadane，複雜度 O(rows² × cols)

五、複雜度分析

此題是動態規劃/貪心思想的經典入門，掌握「捨棄負前綴」的決策邏輯，即可輕鬆解決所有最大子陣列和變體問題。