分治法求最大子數組和：算法原理與 C 語言實現

最大子數組問題是經典的算法面試題，分治法提供了優雅的 O(n log n) 解法，展示了「分解-解決-合併」的算法思想。

問題定義

給定整數數組（含正負數），找出連續子數組的最大和。例如：[-2,1,-3,4,-1,2,1,-5,4] → 最大和為 6（子數組 [4,-1,2,1]）。

分治策略

將數組在中點分為左右兩半，最大子數組只能出現在三種情況：

1. 完全在左半部
2. 完全在右半部
3. 跨越中點（包含左半部尾部和右半部頭部）

遞歸求解前兩種，第三種通過從中點向兩側擴展計算最大跨界和。

算法步驟

MaxSubArray(arr, low, high):
    if low == high: return arr[low]  // 基礎情況
    
    mid = (low + high) / 2
    left_max  = MaxSubArray(arr, low, mid)
    right_max = MaxSubArray(arr, mid+1, high)
    cross_max = MaxCrossingSubArray(arr, low, mid, high)
    
    return max(left_max, right_max, cross_max)

跨界最大和計算

MaxCrossingSubArray(arr, low, mid, high):
    left_sum = -∞
    sum = 0
    for i = mid downto low:
        sum += arr[i]
        if sum > left_sum: left_sum = sum
    
    right_sum = -∞
    sum = 0
    for j = mid+1 to high:
        sum += arr[j]
        if sum > right_sum: right_sum = sum
    
    return left_sum + right_sum

完整 C 實現

#include <stdio.h>
#include <limits.h>

int max_crossing(int arr[], int low, int mid, int high) {
    int left_sum = INT_MIN, sum = 0;
    for (int i = mid; i >= low; i--) {
        sum += arr[i];
        if (sum > left_sum) left_sum = sum;
    }
    
    int right_sum = INT_MIN;
    sum = 0;
    for (int j = mid+1; j <= high; j++) {
        sum += arr[j];
        if (sum > right_sum) right_sum = sum;
    }
    return left_sum + right_sum;
}

int max_subarray(int arr[], int low, int high) {
    if (low == high) return arr[low];
    int mid = (low + high) / 2;
    int left = max_subarray(arr, low, mid);
    int right = max_subarray(arr, mid+1, high);
    int cross = max_crossing(arr, low, mid, high);
    
    int max = left;
    if (right > max) max = right;
    if (cross > max) max = cross;
    return max;
}

int main() {
    int arr[] = {-2, 1, -3, 4, -1, 2, 1, -5, 4};
    int n = sizeof(arr)/sizeof(arr[0]);
    printf("最大子數組和: %d\n", max_subarray(arr, 0, n-1));
    return 0;
}

複雜度分析

• 時間：O(n log n) — 每層遞歸 O(n)，共 log n 層
• 空間：O(log n) — 遞歸調用棧深度

優化方向

Kadane 算法（動態規劃）可達到 O(n) 時間、O(1) 空間，是工程實踐的首選。但分治法在並行計算、教學演示中仍有獨特價值。