最大子序列和問題：O(N) 線性掃描法與 O(N log N) 分治法完整實現

經典算法題「最大子數組和」：Kadane 算法線性掃描 vs 分治遞歸雙重解法

給定整數數組 (含正負數)，找出**連續子數組**的最大和。若全負數，按題目要求可返回 0 (空子數組) 或最大負數。本文提供兩種經典解法完整 C 實現：**O(N) Kadane 線性掃描 (工程首選)** 與 **O(N log N) 分治遞歸 (教學經典)**，附隨機測試驅動代碼。

問題定義

輸入: int a[N] (N=100, 含正負隨機數)
輸出: 最大連續子數組和
約束: 子數組必須連續；允許空子數組和為 0

解法一：Kadane 算法 — O(N) 線性掃描 (最優)

核心洞察：維護「以當前元素結尾的最大子數組和」`thisSum`。若 `thisSum < 0`，拋棄前綴 (負數拖累後續)，歸零重新開始。

int MaxSubSum_HighSpeed(int a[], int N) {
    int thisSum = 0, maxSum = 0;
    for (int i = 0; i < N; i++) {
        thisSum += a[i];           // 延伸子數組
        if (thisSum > maxSum)      // 更新全局最大
            maxSum = thisSum;
        else if (thisSum < 0)      // 負債重組
            thisSum = 0;
    }
    return maxSum;
}

正確性證明草圖：最優子數組必不以負前綴開頭 (否則去掉前綴更大)；算法枚舉所有「非負前綴結尾」的子數組和，覆蓋最優解。

複雜度：時間 O(N)，空間 O(1)。—— **生產環境唯一推薦**。

解法二：分治遞歸 — O(N log N) 教學經典

策略：將數組二分，最大子數組必位於三種情況之一：

1. 完全在左半部
2. 完全在右半部
3. **跨越中點** (含左半部尾部 + 右半部頭部)

遞歸求解左右，線性掃描求跨越中點最大和，取三者最大。

// 三數取最大
int Max3(int a, int b, int c) {
    if (a >= b && a >= c) return a;
    if (b >= a && b >= c) return b;
    return c;
}

// 遞歸核心
int MaxSubSequenceSum(int a[], int left, int right) {
    if (left == right) {           // 基例：單元素
        return (a[left] > 0) ? a[left] : 0;  // 允許空子數組返回 0
    }
    int center = (left + right) / 2;
    int maxLeftSum  = MaxSubSequenceSum(a, left, center);
    int maxRightSum = MaxSubSequenceSum(a, center + 1, right);

    // 跨越中點：向左掃描最大尾部和
    int maxLeftBorderSum = 0, leftBorderSum = 0;
    for (int i = center; i >= left; i--) {
        leftBorderSum += a[i];
        if (leftBorderSum > maxLeftBorderSum)
            maxLeftBorderSum = leftBorderSum;
    }
    // 向右掃描最大頭部和
    int maxRightBorderSum = 0, rightBorderSum = 0;
    for (int i = center + 1; i <= right; i++) {
        rightBorderSum += a[i];
        if (rightBorderSum > maxRightBorderSum)
            maxRightBorderSum = rightBorderSum;
    }

    return Max3(maxLeftSum, maxRightSum, maxLeftBorderSum + maxRightBorderSum);
}

// 入口封裝
int MaxSubSum(int a[], int n) {
    return MaxSubSequenceSum(a, 0, n - 1);
}

完整可運行測試程序

#include 
#include 
#include 

#define MAX_NUM 100

// 簡易隨機數生成 (替代原文 random_n.h)
void random_n(int a[], int n) {
    srand((unsigned)time(NULL));
    for (int i = 0; i < n; i++)
        a[i] = rand() % 200 - 100;  // -99 ~ 100
}

int main() {
    int a[MAX_NUM];
    random_n(a, MAX_NUM);

    // 算法 1: 線性掃描
    int max1 = MaxSubSum_HighSpeed(a, MAX_NUM);
    // 算法 2: 分治遞歸
    int max2 = MaxSubSum(a, MAX_NUM);

    printf("Array: ");
    for (int i = 0; i < MAX_NUM; i++) printf("%d ", a[i]);
    printf("\n");

    printf("Kadane O(N)      : %d\n", max1);
    printf("Divide-Conquer O(NlogN): %d\n", max2);
    printf("Results match: %s\n", (max1 == max2) ? "YES" : "NO");

    return 0;
}

測試輸出示例

Array: 12 -45 78 23 -100 56 12 -3 90 -10 ...
Kadane O(N)      : 245
Divide-Conquer O(NlogN): 245
Results match: YES

兩種算法深度對比

擴展：記錄最大子數組邊界 (Kadane 變體)

int MaxSubSum_WithRange(int a[], int N, int *outL, int *outR) {
    int thisSum = 0, maxSum = 0;
    int curL = 0, bestL = 0, bestR = -1;  // 空子數組標記
    for (int i = 0; i < N; i++) {
        thisSum += a[i];
        if (thisSum > maxSum) {
            maxSum = thisSum;
            bestL = curL;
            bestR = i;
        } else if (thisSum < 0) {
            thisSum = 0;
            curL = i + 1;  // 下一個元素作為新起點
        }
    }
    if (outL) *outL = bestL;
    if (outR) *outR = bestR;
    return maxSum;
}

總結

1. 工程首選 Kadane O(N)：單次遍歷、常數空間、易維護、易擴展邊界記錄。
2. 分治 O(N log N) 適合教學展示分治思想、或構建區間最大子數組和段樹 (需修改合併邏輯)。
3. 全負數處理：本實現返回 0 (空子數組)。若題目要求返回最大負數，將初始 `maxSum = a[0]`、`thisSum = a[0]` 並調整判斷邏輯。
4. 在線算法特性：Kadane 可流式處理數據流，無需全量存儲，適合嵌入式/大數據場景。

1. 上一篇文章： C語言輸入輸出格式控制大全：printf/scanf 格式符、標志、寬度、精度完整速查表
2. 下一篇文章： C語言賦值與自增是原子操作嗎？從汇編、CPU流水線、總線鎖定深度解析

關於C語言

Muduo網絡編程示例之八：Timing Wheel 踢掉空閒連接的優雅實現

兩種朴素做法的缺陷 全域掃描：每秒遍歷所有連線檢查 now

實時系統核心難題：優先級反轉與優先級繼承機制圖解

在基於優先級搶佔的實時操作系統（RTOS）中，優先級反轉 是

C 語言學生成績管理系統：完整實現與功能演示

系統概覽 基於 C 語言實現的控制台學生成績管理系統，採用文

C語言 if 語句完全指南：三大形式、嵌套陷阱與最佳實踐

if 是 C 語言構建分支結構的核心語句，提供三種基本形式，