動態規劃演算法例題

A. 演算法面試題——動態規劃Kadane』s algorithm

動態規劃是大公司面試必考的演算法題。其中，「最大子序和」是其中的經典：

面試官：年輕人，前面表現的不錯嘛！看下這道題，給你這個數組[-2, 1, -3, 4, -1, 2, 1, -5, 4]，找到其中和最大的連續子數組，返回最大值。

我：

使用Kadane』s Algorithm解決這個問題。Kadane』s Algorithm可以簡單理解為動態規劃的一種應用，它通過維護兩個變數：localMax和globalMax，來計算連續子數組的最大和。localMax表示以當前元素結尾的子數組的最大和，而globalMax則記錄遍歷過程中發現的最大值。

我們以數組[-2, 1, -3, 4, -1, 2, 1, -5, 4]為例，從左到右遍歷數組。

當遍歷到元素4時，localMax為4（因為4是當前元素），globalMax也更新為4（因為這是遍歷到的第一個元素）。

遍歷到元素-1時，我們考慮兩種情況：
1. 包括前面的元素4，即localMax更新為4 + (-1) = 3。
2. 不包括前面的元素4，即從元素-1開始新的子數組。由於-1 > 3，我們選擇-1作為新的localMax。
因此，globalMax更新為-1。

遍歷到元素2時，localMax為2（因為2 > 1），globalMax更新為2。

遍歷到元素1時，localMax更新為3（因為3 > 2 + 1），globalMax也更新為3。

遍歷到元素-5時，我們考慮兩種情況：
1. 包括前面的元素3，即localMax更新為3 + (-5) = -2。
2. 不包括前面的元素3，即從元素-5開始新的子數組。由於-5 < 3，我們選擇3作為新的localMax。
因此，globalMax更新為3。

遍歷到元素4時，localMax為4（因為4 > 3 + 4），globalMax更新為4。

最終，我們得到數組的最大子序和為4。

動態規劃和Kadane』s Algorithm在解決「最大子序和」問題時，通過維護局部最優解和全局最優解，避免了暴力演算法中的重復計算，大大提高了效率。

理解Kadane』s Algorithm的關鍵在於，它通過比較當前元素和當前元素加上前面元素的最大和，來決定是否更新局部最優解。這樣，我們不僅避免了重復計算，還能在遍歷過程中不斷更新全局最優解。

此外，Kadane』s Algorithm在解決類似問題時，如「買賣股票的最佳時機」，同樣可以應用動態規劃的思想，通過維護局部最優解和全局最優解，來找到最優策略。

動態規劃和Kadane』s Algorithm是解決一系列動態規劃問題的有效工具，通過理解和應用這些演算法，可以大大提高解決問題的效率和准確性。