環狀陣列最大子陣列和的 Java 實現解析

環狀陣列最大子陣列和的 Java 實現解析

在演算法題目中，「最大子陣列和」是經典問題，而當陣列變成環狀（首尾相連）時，解法需要額外考慮跨越邊界的子陣列。本文將詳細解析一種基於 Kadane 演算法改良的實現思路，並附上完整 Java 代碼與測試結果。

核心設計思想

解決環狀陣列最大子陣列和，關鍵在於將環狀問題轉化為兩次線性掃描：

1. 第一次掃描（非環狀情況）：直接套用 Kadane 演算法，遍歷原始陣列 a[]，維護當前累加和 sum 與歷史最大值 max。若 sum < 0 則歸零，最終得到不跨越邊界的最大子陣列和。
2. 構造環狀陣列：找出原陣列中的最小值及其下標 j，以此為分割點，將陣列重組為新陣列 b[]：先複製 a[j] 到 a[n-1]，再複製 a[0] 到 a[j-1]。這相當於在最小值處「剪開」環，使原本跨越首尾的子陣列在新陣列中變為連續段。
3. 第二次掃描（環狀情況）：在重組後的陣列 b[] 上再次執行 Kadane 演算法，初始 max 設為第一次掃描的結果。最終得到的 max 即為環狀條件下的最大子陣列和。

完整 Java 代碼實現

package ketang;
import java.util.*;

public class SumArray {
    public static void main(String[] args) {
        Scanner sca = new Scanner(System.in);
        System.out.println("輸入整數陣列數的個數");
        int num = sca.nextInt();
        int a[], b[];
        a = new int[num];
        b = new int[num];
        System.out.println("輸入陣列的數");
        int i;
        for (i = 0; i < num; i++) {
            a[i] = sca.nextInt();
        }
        int t, j = 0, sum = 0, max = a[0];
        // 第一次掃描：非環狀最大子陣列和
        for (i = 0; i < num; i++) {
            sum += a[i];
            if (max < sum) max = sum;
            if (sum < 0) sum = 0;
        }
        // 實現首尾相接：尋找最小值作為分割點
        int min = a[0];
        for (i = 0; i < num; i++) {
            if (min > a[i]) {
                min = a[i];
                j = i;
            }
        }
        t = j;
        i = 0;
        while (j < num) { b[i++] = a[j++]; }
        j = 0;
        while (j < t) { b[i++] = a[j++]; }
        // 第二次掃描：環狀最大子陣列和
        sum = 0;
        for (i = 0; i < num; i++) {
            sum += b[i];
            if (max < sum) max = sum;
            if (sum < 0) sum = 0;
        }
        System.out.println("最大子陣列和為 " + max);
    }
}

執行結果展示

程式運行截圖如下，展示了輸入陣列與輸出最大和的過程：

編程總結

此題核心難點在於「如何找到連成環的關鍵位置」。通過選取最小值作為分割點重組陣列，巧妙將環狀問題轉化為兩次標準的最大子陣列和問題，體現了演算法轉化思想的靈活運用。