最大子序列和問題：O(n) 演算法解析與 Java 實作

問題描述

給定一組整數序列，找出連續子序列的最大和。只需回傳最大和，不需回傳子序列本身。

範例

• 序列：-2, 11, -4, 13, -5, -2 → 最大子序列和為 20（11 + -4 + 13）
• 序列：-6, 2, 4, -7, 5, 3, 2, -1, 6, -9, 10, -2 → 最大和為 16

O(n) 線性解法（Kadane 演算法）

核心思想：遍歷陣列，維護「以當前元素結尾的最大子序列和」（thisSum）與「全域最大和」（maxSum）。若 thisSum 變為負數，歸零重新累加，因為負數只會拖累後續總和。

public static int maxSubSum(int[] a) {
    int maxSum = a[0];
    int thisSum = 0;
    for (int j = 0; j < a.length; j++) {
        thisSum += a[j];
        if (thisSum > maxSum) {
            maxSum = thisSum;
        } else if (thisSum < 0) {
            thisSum = 0;
        }
    }
    return maxSum;
}

關鍵點

• 時間複雜度 O(n)，只需單次遍歷。
• 空間複雜度 O(1)，僅使用常數額外空間。
• 適用於含正負數的整數陣列；若全為負數，回傳最大（最接近零）的負數。

延伸思考

若需同時輸出子序列的起始與結束索引，可在更新 maxSum 時記錄位置；若允許空子序列（和為 0），需將 maxSum 初始化為 0 並調整邏輯。