想像你有一排數字，這些數字可以是正數、負數或零。例如：[-2, 1, -3, 4, -1, 2, 1, -5] 我們想在這排數字中，找到連續的一段，使得這段數字的總和最大。

• 例如，[4, -1, 2, 1] 這一段的和是 4 - 1 + 2 + 1 = 6。
• [1, -3] 這一段的和是 1 - 3 = -2。
• 單獨一個數字也可以是一段，例如 [4] 的和是 4。

我們的目標就是找出那個最大的和。

如果用「笨」方法？

最直觀的方法可能是：

1. 找出所有可能的連續子序列（例如，從第1個開始，長度為1、為2、為3...；從第2個開始，長度為1、為2、為3...）。
2. 計算每一個子序列的和。
3. 比較所有這些和，找出最大的。 這個方法可行，但如果數字很多，可能的子序列會非常非常多，計算起來會很慢 (大約是 O(N2) 到 O(N3) 的時間)。

Kadane's Algorithm 的聰明之處 (核心思想)

Kadane 演算法說：我們不需要看所有的子序列！我們可以從頭到尾掃描一次數列，同時記住一些關鍵資訊。

想像你正走過這排數字，手裡拿著兩個計分板：

1. 目前走到這裡的最佳連續和 (current_max_ending_here)：
   • 這個計分板記錄的是「如果子序列必須在我現在站的這位子結束，那麼它能得到的最大和是多少」。
2. 到目前為止的全局最佳連續和 (overall_max_so_far)：
   • 這個計分板記錄的是「從我開始走到現在，我看過的所有可能子序列中，最大的那個和是多少」。這就是我們最終想要的答案。

演算法步驟 (一步一步來)：

1. 初始化：

   • overall_max_so_far = 數列的第一個數字。
   • current_max_ending_here = 數列的第一個數字。 (如果數列是空的，或者題目有特殊規定，可能初始化方式不同，但我們先假設數列至少有一個數字)。

2. 遍歷數列： 從數列的第二個數字開始，一個一個往後看。對於你看到的每一個新數字 num：

   • 更新 current_max_ending_here：
     • 思考一下，對於這個新數字 num，讓它作為結尾的子序列，怎樣才能得到最大和？有兩種可能：
       1. 這個 num 自己單獨一段，形成一個新的開始。它的和就是 num 本身。
       2. 把這個 num 接到「以上一個數字結尾的最佳連續和 (current_max_ending_here 的舊值)」後面。它的和就是 舊的 current_max_ending_here + num。
     • 我們取這兩種可能中較大的那一個，作為新的 current_max_ending_here。 current_max_ending_here = max(num, current_max_ending_here + num)
   • 更新 overall_max_so_far：
     • 我們剛剛算出了「以當前數字結尾的最佳連續和」。這個和有沒有比我們先前記錄的「全局最佳連續和」更大呢？
     • overall_max_so_far = max(overall_max_so_far, current_max_ending_here)

3. 結束： 當你看完所有數字後，overall_max_so_far 計分板上的數字，就是整個數列中最大連續子序列的和。

為什麼這樣可行？（處理負數的關鍵）

current_max_ending_here = max(num, current_max_ending_here + num) 這一行是精髓。

• 如果 current_max_ending_here + num 比 num 自己還小，這意味著前面那段 current_max_ending_here 是個「拖油瓶」（它的和是負的，而且負得比較多）。與其帶著這個拖油瓶讓總和變小，不如從 num 自己開始一段新的子序列。
• 這就巧妙地處理了負數的問題：如果一段連續和變成了負數，並且這個負數會讓後續的總和變得更糟，演算法就會「放棄」前面這段，從下一個正數（或較小的負數）重新開始計算。

舉個例子：[-2, 1, -3, 4, -1, 2, 1, -5]

遍歷結束，overall_max_so_far 的值是 6。

處理全為負數的情況：

例如 [-1, -2, -3]

答案是 -1，這是正確的（因為 [-1] 是和最大的子序列）。

總結一下：

Kadane's Algorithm 的核心就是：

1. 一路往前走。
2. 記住「如果我的子序列必須在現在這個點結束，那它最大能是多少？」（current_max_ending_here）
   • 這個值要嘛是當前數字自己，要嘛是當前數字加上「前一個點結尾的最佳和」。
3. 同時，不斷更新「我到目前為止見過的最大的子序列和是多少？」（overall_max_so_far）。

這樣只需要從頭到尾看一遍數列 (O(N) 時間)，用很少的額外記憶體 (O(1) 空間)，就能找到答案！對於中級學生來說，理解這個遞推的想法和「如果累計和變成負的就可能需要重新開始」的直覺是很重要的一步。