7.1 最大區段和

給定一個串列。請問它的眾多區段中，總和最大的和是多少？ 這個最大區段和(maximum segment sum)問題可說是最經典的區段問題。 我們可將其寫成如下的規格：

mss :: List Int -> Int
mss = maximum . map sum . segments 

這幾乎便是問題的字面翻譯：算出所有的區段，對每個區段算其和，然後挑出最大的一個。 (註1) 函數 maximum :: List Int -> Int 的定義見例2.12 . 我們得假設整數中有個 -infty 作為 maximum [] 的結果。若要避免 -infty，可注意到 inits, tails, 和 segments 都不會傳回空串列 --- 它們的型別都可寫成更嚴格的 ListP (List a)。因此我們可改用例2.12 中的 maximumP. 本節的推導稍加修改後即可適用。 當輸入串列長度為 $n$, 這個定義本身是一個時間複雜度為 $O(n^3)$ 的演算法 --- 該串列的區段有 $O(n^2)$ 個，每個都需分別算總和。 我們能導出一個更快的演算法嗎？

前段-後段分解  許多區段問題的推導都以如下方式開頭：將 segments 展開成 inits 與 tails, 並將 maximum 往右推，與 inits 放在一起：

      maximum . map sum . segments
 ===  maximum . map sum . concat . map inits . tails
 ===   {- map f . concat = concat . map (map f) (習題 2.13) -}
      maximum . concat . map (map sum) . map inits . tails
 ===   {- maximum . concat = maximum . map maximum -}
      maximum . map maximum . map (map sum) . map inits . tails
 ===   {- map 融合 （定理2.2） -}
      maximum . map (maximum . map sum . inits) . tails 

細看 maximum . map sum . inits 這個子算式，其意思是「給定一個串列，計算其所有前段的和的最大值」。我們為這個子算式取個名字，令 mps = maximum . map sum . inits，其中 mps 為「最大前段和 maximum prefix sum」的縮寫。經由上述演算，我們得知

  mss = maximum . map mps . tails 

意思是：要找出所有區段的最大和，我們可以對每一個後段，找出其最大前段和。

這是解許多區段問題的常見模式：要解決最佳區段問題，先試著解最佳前段問題。 要算出最佳區段，可對每一個後段，算出其最佳前段。 (註2) 反過來當然也可以。如果我們定義 segments = concat . map tails . inits, 此處的策略就變成「對每個前段，算出其最佳後段」。

使用掃描引理   接下來我們注意到 map mps . tails 這個子算式。回顧掃描引理(6.11 ), 重複如下：

map (foldr f e) . tails = scanr f e = foldr (\x ys -> f x (head ys) : ys) [e] 

如果我們能把 mps 變成一個 foldr， map mps . tails 可改寫為 scanr. 如果該摺的步驟函數只花常數時間，我們就有了一個線性時間的演算法了！

如何把 mps 變成摺呢？由於 inits 是摺，我們可使用摺融合。 此處的計算和例6.9 很類似，我們可以把 map sum 與 maximum 分兩次融合進 inits, 也可以一次把 maximum . map sum 融合進 inits. 這次我們試試看後者。 基底值 maximum (map sum [[]]) = 0. 我們想要尋找滿足融合條件 maxmium (map sum ([] : map (x:) xss)) = step x (maximum (map sum xss)) 的函數 step. 計算如下：

      maximum (map sum ([] : map (x:) xss))
 ===    {- map 與 sum 之定義  -}
      maximum (0 : map sum (map (x:) xss))
 ===    {- map 融合  -}
      maximum (0 : map (sum . (x:)) xss)
 ===    {- sum 之定義 -}
      maximum (0 : map ((x+). sum) xss)
 ===    {- maximum 之定義 -}
      0 ↑ maximum (map ((x+). sum) xss)
 ===    {- maximum . map (x+) = (x+) . maximum -}
      0 ↑ (x + maximum (map sum xss)) 

因此我們推導出了：

      maximum . map sum . inits
 ===  maximum . map sum . foldr (\x xss -> [] : map (x:) xss) [[]]
 ===   {- 摺融合定理，融合條件如上 -}
      foldr (\x s -> 0 ↑ (x + s)) 0 

注意：步驟函數推導的最後一步中，為了將 maximum 往右推，使用了如下的性質

  maximum . map (x+)&= (x+) . maximum     (7.1 )

在 ([RefUndefined]) 的左手邊，我們將一個串列的每個元素都加上 x, 然後取最大值。 性質 ([RefUndefined]) 告訴我們，其實我們可以先取最大值，然後做一個加法即可。 這個步驟允許我們在每一步省下了 $O(n)$ 個加法，是使得整個演算法之所以能加速的關鍵一步。 而 ([RefUndefined]) 的證明只需使用例行的歸納法，但其中的關鍵一步需要如下的分配律：

x + (y ↑ z) &= (x + y) ↑ (x + z)     (7.2 )

加法與max的分配率是使我們能有一個線性時間演算法的關鍵性質。

既然 mps 已經是一個摺，我們可以使用掃描引理：

      maximum . map sum . segments
 ===    {- 上述計算 -}
      maximum . map (foldr (\x s -> 0 ↑ (x + s)) 0) . tails
 ===    {- 掃描引理6.11 -}
      maximum . scanr (\x s -> 0 ↑ (x + s)) 0 

我們得到

mss = maximum . scanr (\x s -> 0 ↑ (x + s)) 0 

這是一個使用線性時間、線性空間的演算法。

藉由程式推導，我們不僅找到了一個較快的演算法，也找出了使得該演算法之所以成立的根本性質。 這使我們能輕易將該演算法推廣：不僅是加法與max，該演算法能用在任何滿足 ([RefUndefined]) 的一組運算元之上。

常數空間   使用掃描引理導出的 mss 能在線性時間內對輸入串列的每個後段算出其 mps （即「最大前段和」）並存放在一個串列中。 方法是使用一個 scanr 將串列由右到左走訪一遍，在每一步將 x 與 mps xs 的值（存放在串列中）相加，並和 0 比大小。 每個 mps 值之中最大的那個，便是我們要的答案。 在函數語言圈內，關於最大區段和的討論大多到此為止：我們已經有了一個漂亮的線性時間演算法了。

若要再挑惕，這個演算法的不盡滿意之處是需要線性的空間 --- scanr 會產生一個中間串列，由 maximum 消掉。 我們有可能把 maximum 與 scanr 融合，得到一個不產生中間串列的演算法嗎？根據摺融合定理，我們將需要找到滿足以下融合條件的函數 step：

 maximum (0 ↑ (x + head ys) : ys) = step x (maximum ys) 

這顯然做不到：從 maximum ys 是無法取出 head ys 的。

這時就用得上組對的技巧了 --- 既然需要 head，就把它一併歸納地算出來吧！ 定義：

  msps = fork maximum head . scanr (\x s -> 0 ↑ (x + s)) 0 

要把 fork maximum head 融入 scanr, 我們依融合條件推導：

     fork maximum head (0 ↑ (x + head ys) : ys)
===    {- fork 之定義 -}
     (maximum (0 ↑ (x + head ys) : ys), head (0 ↑ (x + head ys) : ys))
===    {- maximum 與 head 之定義 -}
     ((0 ↑ (x + head ys)) ↑ maximum ys, 0 ↑ (x + head ys))
===    {- 取出 (maximum ys, head ys) -}
     (\m s -> ((0 ↑ (x + s)) ↑ m, 0 ↑ (x + s))) (maximum ys, head ys)
===    {- 取出重複項 0 ↑ (x + s) -}
     (\m s -> let s' = 0 ↑ (x + s) in (s' ↑ m, s')) (maximum ys, head ys)  

我們得到

mss'' = fst . msps 

msps :: List Int -> (Int × Int)
msps = foldr (\m s -> let s' = 0 ↑ (x + s) in (s' ↑ m, s')) (0,0) 

或著，我們把 msps 的 foldr 定義展開，也許比較容易理解：

msps []      =  (0,0)
msps (x:xs)  =  let  (m,s) = msps xs
                     s' = 0 ↑ (x + s)
                in   (s' ↑ m, s') 

這是一個使用線性時間、常數空間計算最大區段和的演算法。當 (m,s) = msps xs, m 是 xs 的最大區段和，s 則是 xs 的最大前段和。 每考慮一個新元素 x, 最大前段和被更新為 0 ↑ (x + s) --- 如果把 x 接上後仍是正數，x+s 就是最好的前段和，否則最大前段和是空串列的和 0. 新的最大前段和再與 m 比較，得到新的最大區段和。

i, m, s := 0, 0, 0;
do i /= N ->  s := 0 ↑ (X i + s) ;
              m := m ↑ s ;
              i := i + 1
od ;
return m