最大子序列和演算法深度解析：從暴力法到線性時間的演進

最大子序列和演算法深度解析：從暴力法到線性時間的演進

給定一個包含 n 個整數的序列 {a₁, a₂, ..., aₙ}，我們需要找出連續子序列的最大和。具體來說，定義函數 f(i, j) = max{0, Σaₖ}（其中 k 從 i 連續取到 j）。若所有子序列和均為負數，則結果取 0。例如序列 {-1, 2, -3, 4, -2, 5, -8, 3} 的最大子序列和為 4 + (-2) + 5 = 7。

演算法一：暴力枚舉法 O(n³)

最直觀的方法是窮舉所有可能的子序列。設定子序列的左端點 i 和右端點 j，再用第三層迴圈計算 a[i] 到 a[j] 的和。

int Find_MaxSum(int* a, int n) {
    int MaxSum = 0, i, j, k;
    int NowSum;
    for (i = 0; i < n; i++)           // 子序列左端
        for (j = 0; j < n; j++) {     // 子序列右端
            NowSum = 0;
            for (k = i; k <= j; k++)  // 從 a[i] 到 a[j] 重新累加
                NowSum += a[k];
            if (NowSum > MaxSum)
                MaxSum = NowSum;      // 更新最大值
        }
    return MaxSum;
}

三層巢狀迴圈導致時間複雜度為 O(n³)。明顯的缺點是：每次 j 遞增時，都要從頭重新計算子序列和，造成大量重複運算。

演算法二：預儲中間結果 O(n²)

利用前一次計算的結果：當右端點從 j-1 移至 j 時，只需在前一次的和上加上 a[j] 即可，省去內層迴圈。

int Find_MaxSum2(int* a, int n) {
    int i, j, NewSum = 0, MaxSum = 0;
    for (i = 0; i < n; i++) {         // 左端點
        NewSum = 0;
        for (j = i; j < n; j++) {     // 右端點
            NewSum += a[j];           // 利用上一次結果累加
            if (NewSum > MaxSum)
                MaxSum = NewSum;
        }
    }
    return MaxSum;
}

時間複雜度降為 O(n²)，但對於大規模資料仍不夠理想。

演算法三：分治法 O(n log n)

將序列一分為二，最大子序列必在三種情況之一：完全在左半部、完全在右半部、或跨越中間分界線。遞歸求解左右兩側，再從中間向兩側掃描找出跨界最大和，最後取三者最大值。

int Find_MaxSum3(int* a, int low, int high) {
    if (low == high) {                // 遞歸終止條件
        return (a[low] > 0) ? a[low] : 0;
    }
    int mid = (low + high) / 2;
    int LeftSum  = Find_MaxSum3(a, low, mid);
    int RightSum = Find_MaxSum3(a, mid + 1, high);

    // 跨界最大和：從中間向左、向右各掃描一次
    int MaxLeft = 0, MaxRight = 0, temp = 0;
    for (int i = mid; i >= low; i--) {
        temp += a[i];
        if (temp > MaxLeft) MaxLeft = temp;
    }
    temp = 0;
    for (int i = mid + 1; i <= high; i++) {
        temp += a[i];
        if (temp > MaxRight) MaxRight = temp;
    }
    int MidSum = MaxLeft + MaxRight;
    return max(LeftSum, MidSum, RightSum);
}

遞歸關係式：T(n) = 2T(n/2) + O(n)，解得 T(n) = O(n log n)。

演算法四：線上處理 / Kadane 演算法 O(n)

單次掃描即可完成，維護「以當前元素結尾的最大子序列和」。若當前累加和小於 0，則捨棄重置為 0，因為負數只會拖累後續和。

int Find_MaxSum4(int* a, int n) {
    int NewSum = 0, MaxSum = 0;
    for (int i = 0; i < n; i++) {
        NewSum += a[i];
        if (MaxSum < NewSum) MaxSum = NewSum;
        if (NewSum < 0) NewSum = 0;   // 捨棄負數前綴
    }
    return MaxSum;
}

此法只需一次遍歷，時間複雜度 O(n)，空間複雜度 O(1)，是目前已知最優解。核心思想在於「記住關鍵中間結果，避免重複計算」，這正是演算法優化的精髓所在。