#90 淺談 Dynamic Programming (2)

 前面說過 dynamic programming 的應用很多,這一篇文章來說明其中一種應用,Maximun subarray sum.這個問題是在一個整數的 array 裡找一個連續空間的元素,其元素的總和的值是最大的.如下圖:


source: https://www.geeksforgeeks.org/largest-sum-contiguous-subarray/

從 index 2 到 index 6 之間的元素總和等於 7,這個區間是這個 array 裡最大的區間總和. 要解決這個問題其實不難,因為用最直接的暴力法就可以解決了,其程式結構如下:

這一個暴力法的時間複雜度是 O(n*n*n) ,n 是 array 的長度. 如果 n 很小,影嚮不大,但若 n 很大,這一個運算雖然在空間複雜度很表現的很好,但浪費許多 CPU 的運算資源,因為許多加法的計算是重覆了. 將這個問題的時間複雜度降低的方法不只一種,在這篇文章裡,我們用 dynamic programming 的策略來試著降低時間複雜度.如前一篇文章提過的內容,dynamic programming 的策略在於用空間換取時間,所以我們必須找出在什麼地方可以減少重覆的計算.要減少重覆計算之前,我們可以先從暴力法來看到底真正的計算是花在什麼地方了. 從上述的程式碼,你可以看到決定 subarray 的總和值是從最裡面的迴圈來運算的,所以第一圈會計算 start = 0 , end = 0 的總和值,第二圈會計算 start = 0, end = 1 的總和值, 第三圈會計算 start = 0, end = 2 的總和值,以此類推下去.透過觀察,你便能發現第二圈要計算的內容在第一圈已經算過了部份答案,第三圈要計算的內容在第二圈已經算過了部份的答案,因此,最裡面的迴圈其實是重覆了做了許多相加.

Loop 1: -2 

Loop 2: -2 + -3 = -5  (Loop 1 + -3)

Loop 3: -2 + -3 + 4 = -1 (Loop 2 + 4)

Loop 4: -2 + -3 + 4 + -1 = -2 (Loop 3 -1)

因此,透過以上的運算呈現,便能知道最後一個迴圈是可以去除的.我們只要將上一圈計算後的內容先暫存起來,留到下一圈時便能拿出來用,直接做一次加法就可以得到這一圈的答案了.因此,那個查表法的 "表" 也只不是一個臨時的變數,在空間複雜度上並沒有增加,而時間複雜度卻降了一階變成了 O(n*n),如下列的程式碼.

接著,或許你還會問,空間複雜度還仍再降嗎 ? 剛好這一個題目是可以的,它的名字是 Kadane's algorithm,這個演算法在許多讀者還沒出生之前就已經發明了,這演算法能用 O(n) 的時間複雜度解決這問題,而發明人是一位教授,現在已經非常高齡了. 若你晚些才看到這篇文章, Kadane 教授也許不在人世了,我們大家都是站在巨人的肩膀上.

最後,你可能會問這個演算法我們該用在那裡.這完全取決於你是否會遇到類似的題目.如果你遇到一個問題,而這問題剛好可以 Reduce 成 maximum subarray sum 時,Kadane's algorithm 便能幫助你寫一個超快速的程式來解決問題,例如,你老闆要你找出過去十年裡,那幾個連續的月份其營業額是最好的.

Dynamic programming 的策略確實應用在許多地方,未來介紹更多的主題時,一定都還會碰到 dynamic programming 策略所產生的解法.

Share: