最大子數組和問題：從 O(n³) 到 O(n) 的五種算法演進與 Java 實戰

問題定義

給定整數數組 arr[0..n-1]，找出連續子數組 arr[i..j] 使其和最大。若全負數，返回 0（空子數組）。經典輸入：{31, -41, 59, 26, -53, 58, 97, -93, -23, 84} → 最大和 187，區間 [2,6]。

五種算法完整實現與複雜度分析

方法一：三層暴力枚舉 O(n³)

public void maxSubArrayBruteForce(int[] arr) {
    int maxSum = 0, left = -1, right = -1;
    for (int i = 0; i < arr.length; i++) {
        for (int j = i; j < arr.length; j++) {
            int sum = 0;
            for (int k = i; k <= j; k++) sum += arr[k]; // 重複累加
            if (sum > maxSum) { maxSum = sum; left = i; right = j; }
        }
    }
    printResult(left, right, maxSum, arr);
}

缺陷： 內層循環重複計算 sum(i,j)，極度低效。

方法二：雙層循環累加 O(n²)

public void maxSubArrayDoubleLoop(int[] arr) {
    int maxSum = 0, left = -1, right = -1;
    for (int i = 0; i < arr.length; i++) {
        int sum = 0;
        for (int j = i; j < arr.length; j++) {
            sum += arr[j]; // 增量累加
            if (sum > maxSum) { maxSum = sum; left = i; right = j; }
        }
    }
    printResult(left, right, maxSum, arr);
}

優化： 利用 sum(i,j) = sum(i,j-1) + arr[j] 消除內層循環。

方法三：前綴和 + 雙層循環 O(n²)

public void maxSubArrayPrefixSum(int[] arr) {
    int n = arr.length;
    int[] pre = new int[n + 1];
    for (int i = 0; i < n; i++) pre[i + 1] = pre[i] + arr[i]; // 前綴和

    int maxSum = 0, left = -1, right = -1;
    for (int i = 0; i < n; i++)
        for (int j = i; j < n; j++) {
            int sum = pre[j + 1] - pre[i]; // O(1) 區間和
            if (sum > maxSum) { maxSum = sum; left = i; right = j; }
        }
    printResult(left, right, maxSum, arr);
}

優勢： 區間和查詢 O(1)，適合多次查詢場景；但雙層循環仍為 O(n²)。

方法四：分治法 O(n log n)

public int maxSubArrayDivideConquer(int[] arr, int left, int right) {
    if (left > right) return 0;
    if (left == right) return Math.max(arr[left], 0);

    int mid = (left + right) / 2;
    // 跨中點最大和：左側最大後綴 + 右側最大前綴
    int maxLeftSuffix = 0, sum = 0;
    for (int i = mid; i >= left; i--) {
        sum += arr[i];
        maxLeftSuffix = Math.max(maxLeftSuffix, sum);
    }
    int maxRightPrefix = 0;
    sum = 0;
    for (int i = mid + 1; i <= right; i++) {
        sum += arr[i];
        maxRightPrefix = Math.max(maxRightPrefix, sum);
    }
    int crossMax = maxLeftSuffix + maxRightPrefix;

    int leftMax = maxSubArrayDivideConquer(arr, left, mid);
    int rightMax = maxSubArrayDivideConquer(arr, mid + 1, right);

    return Math.max(crossMax, Math.max(leftMax, rightMax));
}

核心思想： 最大子數組要麼在左半部、要麼在右半部、要麼跨越中點。遞歸分解，合併時線性掃描跨中點最大和。

方法五：Kadane 算法 O(n) — 最優解

public void maxSubArrayKadane(int[] arr) {
    int maxEndingHere = 0, maxSoFar = 0;
    int left = -1, right = -1, tempLeft = 0;

    for (int i = 0; i < arr.length; i++) {
        maxEndingHere += arr[i];
        if (maxEndingHere > maxSoFar) {
            maxSoFar = maxEndingHere;
            left = tempLeft;
            right = i;
        }
        if (maxEndingHere < 0) { // 關鍵：負和拋棄，重新開始
            maxEndingHere = 0;
            tempLeft = i + 1;
        }
    }
    printResult(left, right, maxSoFar, arr);
}

Kadane 算法核心不變式圖解

// 遍歷到索引 i 時維護：
// maxEndingHere = 以 arr[i] 結尾的最大子數組和（若 < 0 則歸 0）
// maxSoFar      = 全局最大和
// tempLeft      = 當前候選子數組的起始索引

// 狀態轉移：
// maxEndingHere = max(0, maxEndingHere + arr[i])
// if (maxEndingHere 更新了 maxSoFar) 記錄 left/right

運行結果驗證

輸入: [31, -41, 59, 26, -53, 58, 97, -93, -23, 84]
方法一: Max is from element 2(59) to element 6(97), max sum is 187
方法二: Max is from element 2(59) to element 6(97), max sum is 187
方法三: Max is from element 2(59) to element 6(97), max sum is 187
方法四: Max sum is 187
方法五: Max is from element 2(59) to element 6(97), max sum is 187

變體與擴展

總結

最大子數組和問題是 動態規劃 / 貪心 / 分治 思想的教科書級案例。從 O(n³) 到 O(n) 的演進，本質是 識別並消除重複子問題計算。Kadane 算法僅用 10 行代碼實現了最優時間/空間複雜度，其核心洞見 —— 「負和前綴不可能是最優解的一部分，果斷拋棄重來」 —— 體現了貪心策略的精髓。面試、競賽、工程優化中，請直接使用並熟練變體擴展。