C語言最大和子數組問題：O(n) 動態規劃算法完整實現與索引追蹤增強版

編輯：關於C語言

前言：最大子數組和——經典面試題與工程實用算法

給定含正負整數的數組，求**連續子數組**最大和，要求 O(n) 時間。這是 Kadane 算法標準應用，也是動態規劃「狀態壓縮」的教科書級例子。本文提供基礎版、帶索引追蹤增強版、全負數組邊界處理、完整測試代碼與運行結果圖示。

一、核心算法邏輯

狀態定義：curSum 為以當前元素結尾的最大子數組和。

轉移方程：

curSum = max(curSum + a[i], a[i])
// 等價寫法：
curSum += a[i];
if (curSum < 0) curSum = 0;  // 拋棄負前綴
if (curSum > maxSum) maxSum = curSum;

直觀理解：負數前綴只會拖累後續和，**果斷歸零重新開始**。

二、基礎版實現 (僅求最大和)

void MaxSum(int array[], unsigned int len) {
    if (!array || len == 0) return;
    int curSum = 0, maxSum = 0;
    for (unsigned int i = 0; i < len; i++) {
        curSum += array[i];
        if (curSum < 0) curSum = 0;
        if (curSum > maxSum) maxSum = curSum;
    }
    // 全負數組特殊處理：maxSum 仍為 0，實際應為最大元素
    if (maxSum == 0) {
        maxSum = array[0];
        for (unsigned int i = 1; i < len; i++)
            if (array[i] > maxSum) maxSum = array[i];
    }
    printf("maxSum: %d\n", maxSum);
}

測試數組

int array[] = {1, -2, 3, 10, -4, 7, 2, -5}; // 最大子數組: 3,10,-4,7,2 = 18

運行結果

基礎版運行結果

圖1 基礎版輸出 maxSum: 18

三、增強版：追蹤子數組起止索引

工程中往往需要知道**具體是哪個子數組**。增強版在更新 maxSum 時同步記錄索引。

void MaxSum(int array[], unsigned int len) {
    if (!array || len == 0) return;
    int curSum = 0, maxSum = 0;
    int index_start = 0, index_end = 0; // 最大子數組索引
    int temp_start = 0;                 // 當前候選子數組起始

    for (unsigned int i = 0; i < len; i++) {
        curSum += array[i];
        if (curSum < 0) {
            curSum = 0;
            temp_start = i + 1; // 下一個元素作為新起點
        }
        if (curSum > maxSum) {
            maxSum = curSum;
            index_start = temp_start;
            index_end = i;
        }
    }

    // 全負數組處理
    if (maxSum == 0) {
        maxSum = array[0];
        index_start = index_end = 0;
        for (unsigned int i = 1; i < len; i++) {
            if (array[i] > maxSum) {
                maxSum = array[i];
                index_start = index_end = i;
            }
        }
    }

    // 輸出結果
    printf("index_start: %d\nindex_end: %d\n", index_start, index_end);
    for (int i = index_start; i <= index_end; i++)
        printf("%d\t", array[i]);
    printf("\n\nmaxSum: %d\n", maxSum);
}

運行結果

增強版運行結果

圖2 增強版輸出索引 2~6，子數組 3 10 -4 7 2，最大和 18

四、算法正確性證明草圖

最優子結構：最大子數組要么以當前元素結尾，要么不包含當前元素。
貪心選擇：若前綴和 < 0，延長它絕不優於從下一個元素重新開始。
循環不變量：第 i 輪結束時，maxSum 是 a[0..i] 中最大子數組和，curSum 是以 a[i] 結尾的最大子數組和 (或 0)。

五、變體與擴展

環形數組最大子數組和：總和 - 最小子數組和 (需排除全選情況)。
二維矩陣最大子矩陣和：枚舉上下行，壓縮為一維數組套用 Kadane，O(rows^2 * cols)。
最大乘積子數組：維護 maxEndingHere 和 minEndingHere (負負得正)。
流式處理：算法天然支持流式輸入，無需存儲全量數據。

六、總結

Kadane 算法以 O(n) 時間、O(1) 空間完美解決最大子數組和問題。**負前綴歸零**是核心洞見，**索引追蹤**只需同步記錄起點終點。**全負數組**邊界情況必須顯式處理。這個算法是動態規劃、貪心、狀態壓縮思想的最佳入門教材，也是工程中流式數據異常檢測、信號處理、金融序列分析的實用工具。