7.3 參考資料
最大區段和 對試圖推銷程式推導的人來說，最大區段和問題幾乎有模範問題該有的一切特質： 目標不難理解，但又不容易一眼看出怎麼解得快； 大部分的推導過程都能用很形式化、依符號推導的方式進行； 推出的程式有顯著的效率提升。程式僅需短短幾行，乍看之下卻不容易理解為何會正確。 因此最大區段和問題是程式推導圈內常常提及的經典例子。
根據 Bentley 的 Programming Pearls [Bentley 1986] 一書， 最大區段和問題最初由 Brown 大學的 Ulf Grenander 所提出。 他當時正設計一個圖形配對的函式。 其中，具有最大區段和的二維子陣列是圖形中最有可能含有指定樣式的區域。 二維問題比較難解，因此他先考慮一維的情況：
1977 年，[Grenander] 把該問題講給 UNILOGIC 公司的 Michael Shamos 聽， 後者一夜之間就設計出了演算法3. Shamos 不久後告訴我這個問題時，我們都認為那大概就是最好的解法了；... 又幾天後，Shamos 在 Carnegie-Mellon 大學的專題討論會中講了這個問題和它的來龍去脈。 當時在場的統計學家 Jay Kadane 一聽，幾分鐘內就設計出了演算法4.
--- Jon Bentley, Programming Pearls (第一版), 第76頁.
Kadane 的演算法4就是現在廣為人所知的（指令語言版）線性時間解（見第頁）。
Shamos 的演算法3則是一個採取分而治之(divide and conquer)法的演算法：
將陣列分成長度略等的兩半xs ++ ys, 分別計算 xs 與 ys 的最大區段和。
但除此之外，還得考慮跨越 xs 與 ys 的區段。
因此該演算法在遞迴的每一層又多用了兩個迴圈，分別計算 xs 的最大後段和與 ys 的最大前段和，
兩者之和就是橫跨 xs 與 ys 的最大區段和。
（見第頁。）
該演算法使用 $O(n \log n)$ 的時間。
事後回顧，Shamos 其實不需在每層都把最大前段與後段和重頭算起。 我們可用類似組對的想法，對每個子陣列都由下至上地算出以下四個值：最大前段和、最大區段和、最大後段和，以及總和。 如此一來我們可得到一個線性時間演算法。 這可看作給我們的一個暗示：「分而治之」在此也許是不必要的，我們不需要把陣列從中切半。 事實上，把陣列分成頭與尾反而讓事情簡化不少。 Kadane 立刻想出了演算法4，不知是否用了同樣的思路？
我最初是在 Gibbons [1997] 中見到此問題，當時便覺得印象深刻。 Gibbons 的這篇文章是很好的函數程式推導簡介。 Bird et al. [1996] 改用關係 --- 函數的一種擴充 --- 解最大區段和問題，並推廣到其他資料結構。 Mu [2008] 則以最大區段和問題為開端，討論一些有趣的變形：例如有長度限制的最大區段和，和最大平均區段。
Shamos 的最大區段和演算法
以下是我根據個人理解將 Shamos 的演算法3寫成的 Python 程式。
def mss(l,u):
if l > u:
return 0 {-"\quad\color{burntorange}{\mbox{\# 空陣列的情況}}"-}
else if l == u:
return (0 ↑ a[l]) {-"\quad\color{burntorange}{\mbox{\# 單一元素陣列的情況}}"-}
else:
m = (l + u) / 2
{-"\color{burntorange}{\mbox{\# 計算 a[l..m] 的最大後段和}}"-}
sum, maxToLeft = 0, 0
for i in range (m, l-1, -1):
sum = sum + a[i]
maxToLeft = maxToLeft ↑ sum
{-"\color{burntorange}{\mbox{\# 計算 a[m+1..u] 的最大前段和}}"-}
sum, maxToRight = 0, 0
for i in range (m+1, u+1):
sum = sum + a[i]
maxToLeft = maxToRight ↑ sum
maxCrossing = maxToLeft + maxToRight
{-"\color{burntorange}{\mbox{\# 遞迴計算 a[l..m] 與 a[m+1..u] 的最大區段和}}"-}
maxInL = mss(l,m)
maxInR = mss(m+1,u)
return (maxInL ↑ maxCrossing ↑ maxInR)
區段問題 Zantema [1992]