最大子數組和問題：Kadane 算法 Java 實現與測試驗證

最大子數組和問題：Kadane 算法 Java 實現與測試驗證

給定整數數組（含正負數），找出連續子數組最大和。Kadane 算法 O(n) 掃描一次即得最優解，屬於動態規劃思想。

算法邏輯

• 維護 currentSum（以當前元素結尾的最大子數組和）與 maxSum（全局最大和）。
• 遍歷：currentSum = max(num, currentSum + num)；maxSum = max(maxSum, currentSum)。
• 等價寫法：sum += a[i]; if (sum > max) max = sum; if (sum < 0) sum = 0;。

完整代碼

package ketang;
import java.util.Scanner;

public class ArrayMax {
    public static void main(String[] args) {
        Scanner sc = new Scanner(System.in);
        System.out.print("輸入數組長度: ");
        int n = sc.nextInt();
        int[] a = new int[n];
        System.out.println("輸入數組元素:");
        for (int i = 0; i < n; i++) a[i] = sc.nextInt();

        int sum = 0, max = a[0];
        for (int v : a) {
            sum += v;
            if (sum > max) max = sum;
            if (sum < 0) sum = 0;
        }
        System.out.println("最大子數組和為 " + max);
    }
}

測試用例

擴展：輸出子數組索引

int start = 0, end = 0, tempStart = 0;
for (int i = 0; i < n; i++) {
    sum += a[i];
    if (sum > max) { max = sum; start = tempStart; end = i; }
    if (sum < 0) { sum = 0; tempStart = i + 1; }
}
System.out.println("區間 [" + start + ", " + end + "]");