您现在的位置：程式碼之家 >> 編程語言 > >> C語言 >> 關於C語言

最大子序列和（連續子數組）的多種解法解析：從暴力枚舉到線性動態規劃

編輯：關於C語言

最大子序列和問題概述

給定一個包含正負整數的一維數組，找出其中連續子數組的最大和。這是一個經典的算法問題，也是動態規劃和分治策略的典型應用場景。本文將詳細解析四種不同時間複雜度的解法，並提供完整的 C++ 代碼實現。

核心算法思路對比

1. 暴力枚舉法 O(n³)

最直觀的方法是用三層循環：前兩層確定子數組的左右邊界，第三層計算該區間內元素之和並更新最大值。雖然思路簡單，但時間複雜度高達 O(n³)，僅適合極小規模數據。

2. 優化枚舉法 O(n²)

將第三層求和循環合併到第二層中：固定左邊界，右邊界右移時累加當前元素並即時比較。這將時間複雜度降至 O(n²)，但在大數據量下仍不夠優。

3. 分治法 O(n log n)

將數組二分為左右兩半，最大子序列和只能出現在三種情況：完全在左半、完全在右半、或橫跨中間。前兩種遞歸求解，第三種需從中間向兩側擴展求最大前綴和與後綴和。遞歸深度 log n，每層處理 O(n)，總複雜度 O(n log n)。

4. 線性掃描法（Kadane 算法）O(n) —— 最優解

維護兩個變量：current_sum 記錄以當前元素結尾的最大子數組和，max_sum 記錄全局最大值。遍歷數組時，若 current_sum 變為負數則歸零（因負數前綴只會拖累後續和），否則累加當前元素並更新 max_sum。單次遍歷即可得解，空間複雜度 O(1)。

代碼實現與關鍵點

線性算法核心代碼

int MaxSum(int* a, int n) {
    int sum = 0, max = 0;
    for (int i = 0; i < n; ++i) {
        sum += a[i];
        if (sum > max) max = sum;
        else if (sum < 0) sum = 0;
    }
    return max;
}

關鍵細節： 初始 max = 0 意味著若數組全為負數，函數將返回 0（空子數組）。若需返回最大負數，需將 max 初始化為 INT_MIN 並移除 sum < 0 歸零邏輯。

分治法核心代碼

int max3(int a, int b, int c) {
    return max(a, max(b, c));
}

int maxCrossingSum(int a[], int l, int m, int u) {
    int lmax = a[m], lsum = 0;
    for (int i = m; i >= l; --i) {
        lsum += a[i];
        if (lsum > lmax) lmax = lsum;
    }
    int rmax = a[m+1], rsum = 0;
    for (int i = m+1; i <= u; ++i) {
        rsum += a[i];
        if (rsum > rmax) rmax = rsum;
    }
    return lmax + rmax;
}

int maxSubArrayDC(int a[], int l, int u) {
    if (l > u) return 0;
    if (l == u) return a[l];
    int m = (l + u) / 2;
    return max3(maxCrossingSum(a, l, m, u),
                maxSubArrayDC(a, l, m),
                maxSubArrayDC(a, m+1, u));
}