Sofie 舒霏的部落格

Kadane's Algorithm for solving Maximum Subarray

如果你已經知道某 array A 從 「頭」 加到「第 i 個數字」的最大值，

那該 array 從 「頭」 加到「第 ( i +1 ) 個數字」的最大值呢？

只會有兩種選擇喔！

1. A[i+1] － 直接捨棄掉前面的最大值（ex: A[i+1] > 0，但前面得到的最大值是負的，這樣相加反而會 < A[i+1]）
2. A[: i] + A[i+1]－將現在這個值，再加上前面的最大值

這題在 Leetcode - 152 Maximum Subarray (Easy)。

程式碼會長得像以下這樣，超少～

來個流程圖方便理解

因為只有掃過一次 array，所以時間複雜度 = O(n)，而空間複雜度 = O(1)。

來個 Bonus：

若今天面試官更貪心了，除了得到最大值，還想要你回傳該 subarray 呢？

再仔細看一次流程圖，有發現上圖中的「淺黃色區域」是如何得到的嗎？

類似 global_max & local_max 的概念，

這裡我們同樣需要一個 global_start & local_start，

當 global_max 被更新時，就讓 global_start = local_start，而結束的地方呢？就是現在走到的地方。

最後的 end +1，是因為 subarray 應該要包含 A[end]