例題 1.3：總和最大區間問題#
給定一個實數序列，設計一個最有效的算法，找到一個總和最大的區間。這個問題等價於尋找一支股票最長的有效增長期。
作者提出了四種方法，計算複雜度從高到低依次遞減：
方法 1：三重循環 — O(K^3)#
- 遍歷所有可能的區間起點 p 和終點 q 的組合（O(K^2) 種），對每個區間重新求和（O(K)）
- 做了太多無用功，計算量對於幾萬個數據點就高達幾十萬億
方法 2：兩重循環 — O(K^2)#
- 固定起點 p 後，計算從 p 到 q 的區間和時，利用已有的 S(p,q) 只需加上一個新元素即可得到 S(p,q+1)，省去一重循環
- 只需記錄三個中間值：當前區間和、目前最大值 Max、達到最大值的右邊界 r
- 計算量約為十幾億，是方法 1 的上萬分之一
方法 3：分治算法 — O(K·logK)#
- 將序列一分為二，分別求兩個子序列的總和最大區間
- 最大區間要麼在前半部分、要麼在後半部分、要麼跨越中點
- 跨越中點的情況只需 O(K) 時間處理，遞歸深度為 logK
- 計算量約為百萬級，比方法 2 又快了千分之幾
方法 4：正反兩遍掃描 — O(K)#
- 在方法 2 的基礎上改進：先設定區間的左邊界，然後改變右邊界
- 從前往後累加，當累計之和跌到零以下時，確定一個局部最大區間，然後重新開始新的區間
- 從後往前再做一遍反向累計，確定左邊界
- 只需掃描序列兩遍，複雜度為 O(K)，計算量僅為幾萬次
從方法 1 到方法 4，計算量從幾十萬億降低到幾萬。從業者水平上的微小差異，會導致效率相差數個數量級。作者用此題作為 AB（Google 等）公司的面試題，統計結果如下：
- 約 30% 的面試者只想出方法 1
- 約 40% 能想出方法 2
- 15%～ 20% 能想出方法 3 或類似的 O(MlogN) 方法
- 約 10% 能想出線性複雜度的解法
培養算法直覺的三點體會#
- 認識問題邊界：這道例題中，至少要掃描整個序列一次，因此最優解的下界不可能低於線性複雜度
- 檢查是否在做大量無用功：O(N^2) 的算法會把每個元素掃描 N 次並且做 N 次加法，而線性複雜度的算法只需對每個元素做一次加法
- 逆向思維：如果我們已知總和最大區間的左邊界，只需尋找右邊界即可一次掃描完成。把給定的序列倒過來看（從後往前），問題就迎刃而解
逆向思維對計算機從業者非常重要。人的思維很多時候和計算機科學的思維是矛盾的。要成為一流的計算機科學家或工程師，需要有意識地改變自己的思維方式。
要點#
- 分治算法、遞歸、少做無用功、逆向思維
- 不同複雜度的差異是巨大的