2. 最長遞增子序列

2021-06-22 20:45:02 +0800 CST Tags: dp-opt, l.i.s, sequence

問題：給定一個長度 $n$ 的陣列 arr，請在 $\mathcal O(n\log_2n)$ 時間內找出最晚出現的最長嚴格遞增子序列 (longest increasing subsequence)。

解法：

這題是經典的 DP 優化問題，它的遞迴式非常淺白，困難的是優化。定義 len[$k$] 是以第 $k$ 個整數 arr[$k$] 為結尾的 LIS 長度，很明顯地，$\text{len}[k] = 1 + \max\limits_{\ \ \ 1\ \le\ i\ \lt\ k,\\\text{arr}[i]\ \lt\ \text{arr}[k]}\{\ \text{len}[i]\ \}$，如果 naive 的作法依序從 len[1] 填表到 len[n] 通常是 $\mathcal O(n^2)$，那該如何加速呢？
因為我們填表的順序都是由左到右，為了方便起見，我們定義在即將要填入 len[$k$] 的時候 $S_{k-1}$ 是我們要拿來比較的集合，其中元素 $(\ell, a)$ 代表在 arr[1..(k-1)] 這個連續子陣列裡面存在至少一個長度為 $\ell$、結尾的值為 $a$ 的 LIS，那因為每個結尾都會對應到一個長度，所以在未優化之前，$S_{k-1}$ 的大小均為 $k-1$。注意到一旦採用 $(\ell, a)$ 這種表達方式，我們就不再考慮它所對應到的索引值 (LIS 末尾在 arr 的位置) 是多少了，那他媽一點都不重要。
優化方法根據 [1]，在同一個集合 $S_i$ 內如果有兩個數對 $(\ell_x, a_x)$ 和 $(\ell_y, a_y)$ 而且 $\ell_x\le \ell_y$、$a_x\ge a_y$，那麼前者被選上的競爭力遠遠不及後者，因此它就可以從 $S_i$ 之中被拿掉，如此一來對於優化過後的 $S_i$ 內的任意兩相異數對 $(\ell_x, a_x)$、$(\ell_y, a_y)$ 的 $\ell$ 和 $a$ 會同增減 $(\ell_x\lt \ell_y\land a_x\lt a_y$ 或 $\ell_x\gt \ell_y\land a_x\gt a_y)$，而這意味著 $S_i$ 內的數對們勢必會有個穩定的排序。由於 $\ell$ 和 $a$ 比起來有較穩定的值域範圍，即 $\ell\in[1,n]$ 但 $a\in\mathbb Z$，那麼以 $\ell$ 的值為 $S_i$ 經排序過後的索引值是較明智的作法。注意到在之後的文章段落會預設 $S_i$ 是遞增排序，即愈早出現的 $(\ell, a)$ 會有愈小的 $\ell$ 和 $a$。
那麼給定已排序的 $S_{k-1}$ 和 arr[$k$]，要怎麼更新 $S_k$ 呢？如果我們能利用 binary search 找到：
- 兩個 $(\ell, a_\ell), (\ell+1, a_{\ell+1})\in S_{k-1}$ 使得 $a_\ell\lt$ arr$[k]\le a_{\ell+1}$，那麼 len$[k] := \ell+1$，此時原先就有的 $(\ell+1, a_{\ell+1})$ 和新加入的 $(\ell+1,$ arr$[k])$ 會相互較勁，根據 3. 的規則前者會被取代成後者，如此一來就形成了新排序好的 $S_k$，注意到在本例 $|S_k| =$$|S_{k-1}|$。
- 一個 $(\ell, a_\ell)\in S_{k-1}$ 使得 $a_\ell\lt$ arr$[k]$ 但是 $(\ell+1, .)\notin S_{k-1}$，那依然有 len$[k] := \ell+1$，但這個時候與前例不同，我們可以直接把 $(\ell+1,$ arr$[k])$ 加進集合末尾形成 $S_k$ 而不影響排序，注意到在本例 $|S_k| = |S_{k-1}| + 1$。
初始條件 $S_0=\emptyset$ 而 $S_1=(1,$ arr$[1])$。
在整個過程之中 $S_{k-1}$ 的角色都只是在輔助我們用比較快速的方式算出 len[$k$] 而已，它並不實際儲存我們要的 LIS。那麼這題的答案究竟該如何尋找呢？注意到最後的 $S_k$ 其實儲存了這整個陣列 arr 裡面各種可能的 IS 長度所對應到的最小末尾，所以 $S_k$ 的大小就是 arr 的 LIS 長度，又我們在過程中同時也計算了每個 arr[$k$] 的 len[$k$]，只要由後往前依序蒐集首先滿足各階段指定長度的元素，最後就能找到最晚出現的 LIS。

附註：
[1] https://www.csie.ntu.edu.tw/~sprout/algo2018/ppt_pdf/dynamic_programming_2_1.pdf

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26


int dpLen = 0; // S_0 := ∅
int dp[500000]; // dp[k] := 長度為 k 的 LIS 的最小末尾
int len[500000]; // len[k] := 以 arr[k] 為結尾的 LIS 長度

int arr[500000], n; cin >> n; // arr 陣列長度
for (int k=0; k<n; k++) {
    cin >> arr[k]; // 輸入 arr
    int lb = 1, ub = dpLen, index = ub+1;
    while (lb <= ub) { // binary search
        int mid = (lb + ub) / 2;
        if (dp[mid] >= arr[k]) ub = mid - 1, index = mid;
        else lb = mid + 1;
    } // index := ℓ + 1 as defined above
    len[k] = index; // len[k] := ℓ + 1
    dp[index] = arr[k]; // S_k := S_{k-1} \ {(ℓ+1, a_{ℓ+1})} U {(ℓ+1, arr[k])}
    if (index > dpLen) dpLen = index; // |S_k| = |S_{k-1}| + 1
}

cout << dpLen << '\n'; // 印出最後 S_k 的大小 (LIS 的長度)
int stackLen = 0, stacK[500000];
for (n--; n>=0 && dpLen; n--) // 由後往前依序蒐集
    if (len[n] == dpLen) // 首先滿足各階段指定長度的
        stacK[stackLen++] = arr[n], // 元素
        dpLen--;
while (stackLen) // 由前往後印出 LIS 內容
    cout << stacK[--stackLen] << '\n';