Kadane算法是一種用於解決最大子數組和問題（Maximum Subarray Sum Problem）的動態規劃算法。該算法的目標是在給定的整數數組中找到具有最大和的連續子數組。
Kadane算法的時間複雜度為O(n)，其中n是數組的長度，使其成為解決這個問題的高效方法。算法通過遍歷一次數組，不斷更新當前最大子數組和以及全局最大子數組和。在遍歷過程中，對於每個元素，有兩種可能的選擇：將當前元素加入當前子數組中，從而擴展當前子數組；或以當前元素為起點開始一個新的子數組。算法通過比較當前元素和當前元素加上前一個元素的和來決定如何更新當前子數組和，同時跟蹤全局最大子數組和。
Kadane算法的關鍵在於理解maxEndingHere變數的含義，它表示以當前元素為結尾的最大子數組和。通過不斷更新maxEndingHere和maxSoFar，可以在遍歷過程中找到整個數組中的最大子數組和。