陣列課堂練習：最大子陣列和（Kadane 演算法）實作

陣列課堂練習：最大子陣列和（Kadane 演算法）實作

設計思路

給定含正負數的整數陣列，尋找連續子陣列使其和最大。核心邏輯：

1. 遍歷陣列，維護 currentSum（截至目前位置的子陣列和）
2. 若 currentSum 變為負數，捨棄前段，從當前元素重新累加（負數只會拖減後續和）
3. 每步比較 currentSum 與 maxSum，更新最大值及對應區間

完整程式碼

import java.util.Random;

public class ArrayAdd {
    public static void main(String[] args) {
        int[] a = new int[10];
        for (int i = 0; i < 10; i++) {
            a[i] = new Random().nextInt() % 30;
            System.out.print(a[i] + " ");
        }
        System.out.println();

        int maxSum = a[0];
        int currentSum = a[0];
        int start = 0, end = 0, tempStart = 0;

        for (int i = 1; i < 10; i++) {
            if (currentSum < 0) {
                currentSum = a[i];
                tempStart = i;
            } else {
                currentSum += a[i];
            }

            if (currentSum > maxSum) {
                maxSum = currentSum;
                start = tempStart;
                end = i;
            }
        }

        System.out.println("和最大的子陣列為：");
        for (int i = start; i <= end; i++) {
            System.out.print(a[i] + (i == end ? "" : "+"));
        }
        System.out.println("=" + maxSum);
    }
}

修正說明： 原始碼中輸出迴圈使用了未定義的 ary，已修正為 a；並優化了初始化邏輯，避免全負數陣列錯誤。

執行結果範例

總結

解決演算法問題，數學基礎與邏輯推導同樣重要。Kadane 演算法以 O(n) 時間複雜度、O(1) 空間複雜度優雅解決最大子陣列和問題。