較小的結尾有甚麼用?
定義 14.2.1
(嚴格遞增子序列)
的子序列保留原來次序,但可以跳過元素;它由下標 決定。若 ,它便是嚴格遞增的,即每個選中的值都小於下一個。
例如 是 的子序列, 卻不是:6 出現在 2 和 4 之前。
對兩條長度相同的遞增子序列,結尾較小的一條至少同樣容易由未來的值延長。這不表示前面的元素相同,也不表示一組尾值本身是一條子序列。有用的狀態是:分別對每個長度記下最小可能結尾。
定義 14.2.2
(各長度的最小尾值)
對整數輸入 ,令 為已處理前綴中,長度為 的嚴格遞增子序列之最小可能末值。把 放在 tails 的位置 ; 是目前可達的最大長度。空前綴對應空陣列。
尾值嚴格遞增
定理 14.2.3
(最小尾值嚴格遞增)
對每個已處理的前綴,都有 。
證明
(把最優的較長子序列與其前綴比較)
對 ,選一條長度 、末值為 的子序列。它的前 個選中元素構成長度 的子序列,其末值 嚴格小於 。因為 是長度 的最小可達末值,
所以 tails 嚴格遞增。前綴有限,子序列也只有有限多條,因此各最小值確實存在。
這個次序容許二分搜尋。讀到新值 時,找首個 tails[j] >= x 的位置 j;若沒有,令 j = len(tails)。以 取代該尾值,或在末端加入 。
定理 14.2.4
(每個元素只改變一個最小尾值)
設 j 為首個滿足 tails[j] >= x 的位置;若沒有,則 j 為 len(tails)。讀入 後,長度 j+1 的最小尾值變為 (被取代,或在末端新增),而其他每個長度的最小尾值都不變。
證明
(只有長度 j 加一的狀態可能改善)
讀取 前,j 之前的尾值都小於 。若 j>0,可以把 接到一條以 tails[j-1] 結尾、長度為 j 的子序列;若 j=0, 本身構成長度一。因此長度 j+1、以 結尾的子序列存在。
對任何較短長度,舊的最小尾值已小於 ,以 結尾不會改善它。對大於 j+1 的長度,若有子序列以 結尾,其先前部分至少有長度 j+1 且末值小於 。若 j 位於舊陣列內,該長度的最小尾值已至少為 ,產生矛盾;若 j 在末端,舊前綴根本沒有更長的子序列。所以只有長度 j+1 的狀態可能改善或新出現。取代或追加後,各項仍有原來的最小尾值意義。
證明透視
嚴格性與已排序性在哪裏被用到
這個證明靠兩個前面的事實。尾值嚴格單調,使二分搜尋有效,並給出「j 之前的尾值都小於 ,而 tails[j] 不是」。不平凡的一步在最後:若有長度大於 j+1 且以 結尾的子序列,它會含有一條長度 j+1、末值嚴格小於 的前綴,而 tails[j] >= x 排除了這種情況,所以較長的狀態不會改變。「首個至少等於」的規則正是嚴格性所需要的:等於 的尾值不能被 延長,所以必須被取代而不是跳過。若改用「首個嚴格大於」的規則,證明便會在「接在每個較短尾值之後都可以以 結尾」處失效。
須找第一個至少等於 的尾值,而非第一個嚴格大於 的尾值。相等值不能延長嚴格遞增子序列。對 ,尾值陣列始終為 ,答案是一。非遞減子序列是不同問題,應找第一個嚴格大於 的尾值。
概念視角組合
尾值就是各堆的堆頂
把每個項目放到最左邊、堆頂至少為 的一堆上;若沒有這樣的堆,就開一個新堆。於是每一堆都是非遞增的,而各堆堆頂正是 tails。對 ,各堆為 、、。遞增子序列中的兩項不會落在同一堆,所以 堆就證明不存在長於 的遞增子序列。
常見錯誤
(對嚴格鏈使用首個嚴格大於的尾值)
若以 bisect_right 代替 bisect_left,輸入 會得到 bisect_right([2],2)=1,於是再次追加 ,尾值變成 ,再變成 。報告的長度 是錯的:任何兩個相等的值都不能構成嚴格遞增子序列,正確長度為 。
尾值陣列不一定是子序列
反例模式
各最小尾值的見證可能互不相容
依次處理 ,尾值陣列為
最後 雖然遞增,其來源下標依次是 3、4、2(由零開始),不是輸入的子序列。尾值 6 的長度三見證是 ;後來較短長度的取代是獨立最優值。
陣列長度仍給出正確的最大長度。要輸出實際下標,須在每個元素處理時,記錄它延長了哪個較早的見證。
取代尾值時保存見證
以 end[j] 記錄達到 tails[j] 的一條見證之末項輸入下標;prev[i] 記錄第 項選用的前驅下標。當 放入 j>0 時,先設定 prev[i] = end[j-1],然後才取代尾值或末項下標。若 j=0,便沒有前驅;接著設定 end[j]=i,必要時追加。
定理 14.2.5
(已記錄的前驅鏈給出最優見證)
設 end[j] 與 prev 如上維護。每處理一個元素後,end[j] 都是一條真實的、長度為 j+1、末值為 tails[j] 的嚴格遞增子序列的末項下標。從 end[L-1] 沿 prev 回溯並反轉,得到最大長度 的嚴格遞增子序列。
證明
(後來的取代不會破壞已記錄的前驅鏈)
按輸入位置歸納。每個 end[j] 都指向已處理前綴中一條真實的長度 j+1 遞增子序列,其末值是 tails[j]。若新位置 j>0,end[j-1] 的見證更早出現,末值又嚴格小於 ;接上目前元素得到有效的長度 j+1 見證。j=0 則是一項見證。
新的 prev[i] 儲存固定的輸入下標,不是指向可變的尾值欄位。之後即使 end[j-1] 改變,也不會改變已記錄的前驅。從最後的 end[L-1] 沿鏈回溯並反轉,得到下標嚴格遞增、值亦嚴格遞增的子序列。它有長度 ,而尾值不變量已證明這是最優長度。
from bisect import bisect_left
def longest_increasing_subsequence(a):
tails, end = [], []
prev = [-1] * len(a)
for i, x in enumerate(a):
j = bisect_left(tails, x)
if j > 0:
prev[i] = end[j - 1]
if j == len(tails):
tails.append(x)
end.append(i)
else:
tails[j] = x
end[j] = i
indices = []
current = end[-1] if end else -1
while current != -1:
indices.append(current)
current = prev[current]
indices.reverse()
return indices, [a[i] for i in indices]
例題 14.2.6
(在短輸入上追蹤三個陣列)
對 執行程式,記錄每個元素之後的 tails、end 和新的 prev。
| 元素 | j | prev[i] | tails | end | |
|---|---|---|---|---|---|
| 0 | 3 | 0 | |||
| 1 | 5 | 1 | 0 | ||
| 2 | 6 | 2 | 1 | ||
| 3 | 2 | 0 | |||
| 4 | 4 | 1 | 3 |
最後 end[2]=2,prev[2]=1,prev[1]=0,所以見證下標為 ,值為 。下標 的值 的前驅下標是 ,構成有效的長度二鏈 ,雖然這條鏈沒有延長到長度三。
例題 14.2.7
(相等值:一個邊界情況)
對 ,第一個元素給出 tails 和 end 。對 ,首個至少為 的尾值在位置 ,所以該尾值被 取代,prev[1]=-1,end[0]=1,對下標 同樣處理。最終 tails 為 ,長度為 ,重建返回下標 和值 。空輸入使 end 為空,current=-1,並返回兩個空列表。
例題 14.2.8
(取代尾值不得破壞已記錄的鏈)
對 執行程式。元素 :tails 。元素 (,j=0):tails ,end 。元素 (,j=1):prev[2]=end[0]=1,tails ,end 。元素 (,j=1):prev[3]=end[0]=1,並取代 :tails ,end 。元素 (,j=2):prev[4]=end[1]=3,所以 tails ,end 。從下標 沿鏈回溯得 ,下標為 ,值為 。連結 prev[4]=3 指向長度二目前的持有者 ,而不是被取代的下標 處的值 。
輸入須為整數序列;函數不修改它。結果是一組最優下標及其值,不保證字典序最小。空輸入返回兩個空列表。對 ,最終長度三的末項仍是下標 2,沿已記錄前驅可得下標 和值 。
計算工作量和輸出
命題 14.2.9
(尾值搜尋的成本)
對 個元素,此實作需要 次比較及 個儲存項目;重建長度 的見證需 時間。
證明
(二分搜尋與儲存陣列)
個元素各在至多 個項目的陣列中做一次二分搜尋,需要 次比較,另加常數次賦值。陣列 tails、end、prev 及輸出的下標列表各至多有 個項目。重建時每一步沿一條鏈走一步,共 步,再反轉長度 的列表。
這些是項目和比較次數界;任意大整數比較的位元成本須另計。只求長度時可省略前驅陣列,但輸出見證需要額外資訊與正確性論證。
此方法不計算最優子序列的數量;帶權重或間距限制的變體也須修改狀態及證明。「嚴格遞增」決定二分比較和見證條件。
常見錯誤
(期望得到某個特定的最優解)
對 , 和 的長度都是最優的三。程式把長度二的尾值 取代為 ,返回下標 ,即 。此算法證明得到的是一條最長鏈,而不是字典序最小或最早的那一條。
練習與解答
快速檢查
(處理 。嚴格版本答案是多少?非遞減版本呢?)
逐個元素追蹤尾值陣列。
解答 · 答案
tails 始終為 ,嚴格長度為 1。三個值可構成長度 3 的非遞減子序列;更新須找首個大於 的尾值。
快速檢查
(為甚麼 不是 的有效見證?)
看看這三個值在輸入中的位置。
解答 · 答案
來源下標是 ,並非遞增;各個最優尾值未必來自同一條時間順序鏈。
快速檢查
(為 給出最優見證,並解釋後來取代尾值為何不破壞它。)
處理 和 時記錄了哪些連結?
解答 · 答案
下標 給出 。處理 5 和 6 時記錄的前驅下標,不會因後來取代長度一、二的末項而改變。
快速檢查
(為甚麼嚴格遞增使用 bisect_left?)
當 等於某個現有尾值時應該怎樣?
解答 · 答案
它取代第一個等於 的尾值,而不是追加相等值;嚴格遞增鏈只能延長小於 的尾值。
快速檢查
(給出處理 之後的 tails 及所報告的長度。)
每個元素都不大於現有的尾值。
解答 · 答案
處理 後為 。對 ,首個至少為 的尾值在位置 ,得 ;對 得 。報告的長度為 ,這是正確的,因為沒有任何兩個值是遞增的。
證明分成兩層:最小尾值保證最優長度,固定的前驅下標則提供達到該長度的真實子序列。