# 最長遞增子序列 ## Longest Increasing Subsequence ---- ### 小知識 #### Subsequence 子序列 -> 不用連續 #### Subarray 子串 -> 要連續 --- ## [題目敘述](http://www.tcgs.tc.edu.tw:1218/ShowProblem?problemid=b032) 給一個長度為 $N$ 的正整數序列 $A$ 求最長嚴格遞增子序列長度 即求一序列 $B$ 滿足 $B_1<B_2<B_3 ...<B_k$ ( $k$ 即為答案) $A_{B_1}<A_{B_2}<A_{B_3}...<A_{B_k}$ >$N<=100$ ---- ### Sample ``` A = 9 3 7 4 5 2 6 B = 2 4 5 7 // （位置）不一定是唯一 LIS = 3 4 5 6 // （內容）不一定是唯一 k = 4 ``` --- ### 怎麼寫？ 按照慣例，設 $dp[i]$ 為由左到右 最後一個位置選 $i$ 的最大長度 最後答案為 $max$ { $dp[i]$ } { $1<=i<=N$ } ---- ### 轉移？ $dp[i]=1+max$ { $dp[j]$ } { $j<i$ , $A_j<A_i$ } 簡單來說，就是在滿足 1. 位置在自己前面 2. 數字比自己小 的 $dp[j]$ 中選一個最大的，接在他後面 ---- ### 實作 ```cpp= #include<iostream> using namespace std; const int N=105; int n,ans,a[105]; int main(){ cin>>n; for(int i=1;i<=n;i++) cin>>a[i]; for(int i=1;i<=n;i++) for(int j=0;j<i;j++) if(a[j]<a[i]){ dp[i]=max(dp[i],1+dp[j]); ans=max(ans,dp[i]); } cout<<ans<<endl; } ``` 複雜度？ $O(N^2)$ --- ## 你以為醬就結束了嗎 ---- ### [再來一題](https://cses.fi/problemset/task/1145/) > $N<=2\times10^5$ ### 嗨呀！！！ 不能 $O(N^2)$ 了怎麼辦？ ---- ### 直接看做法 1. 維護一個嚴格遞增序列 $X$ 2. 從左到右遍歷 $A_i$ ```cpp= if( A[i] > X 中所有元素){ 將 A[i] 放到 X 的最後 // 情況 1 } else{ 將 X 中第一個大於等於 A[i] 換成 A[i] // 情況 2 } ``` ---- ### 看個栗子（？ ``` A = 9 3 7 4 5 2 6 ------------------- i=1 A[i]=9 X是空的 -> 情況 1 X = 9 // 把 9 放到 Ｘ 的最後 ------------------- i=2 A[i]=3 3 < 9 -> 情況 2 X = 3 // 把 9 換成 3 ------------------- i=3 A[i]=7 7 > 3 -> 情況 1 X = 3 7 // 把 7 放到 Ｘ 的最後 ------------------- i=4 A[i]=4 4 < 7 -> 情況 2 X = 3 4 // 把 7 換成 4 ------------------- i=5 A[i]=5 5 > 4 -> 情況 1 X = 3 4 5 // 把 5 放到 Ｘ 的最後 ------------------- i=6 A[i]=2 2 < 3 -> 情況 2 X = 2 4 5 // 把 3 換成 2 ------------------- i=7 A[i]=6 6 > 5 -> 情況 1 X = 2 4 5 6 // 把 6 放到 Ｘ 的最後 ``` ---- ### $X$ 能幹嘛 1. $X$ 的長度即為 LIS 的長度 2. $X$ 不是真正的 LIS 剛剛求出的 $X$ 是 2 4 5 6 但真正的 $LIS$ 是 3 4 5 6 ---- ### 順便一提 $dp[i]$ 就是 $A_i$ 放進 $X$ 的位置 比如說： $A_i$ 放在 $X$ 中的第 $2$ 個位置， $dp[i]=2$ --- ### 另一種做法 其實我們想要找的就是 $max$ { $dp[j]$ } { $j<i$ , $A_j<A_i$ } 因此我們可以用資料結構來維護這個東西 需要的操作有 1. 單點改值 2. 區間求最大值 在由前往後遍歷時，對於每個 $A[i]$ 維護最大的 $dp[i]$ 每次要求 $dp[i]$ 時，在 $0$ ~ $A[i]$ 中取 $dp[j]$ 最大值 $+1$ 就可以了 可以用 BIT 或 線段樹 或其他神秘的資結 --- ### 怎麼求真正的 LIS 如果有一個 $A_j$ 滿足： $A_j<A_i$ 和 $dp[j]=dp[i]-1$ 那麼 $A_i$ 就可以接在 $A_j$ 的後面 ---- ### 再來個栗子 ``` A : 9 3 7 4 5 2 6 dp : 1 1 2 2 3 1 4 ``` 對於第 $4$ 個位置， $A_4=4$ , $dp[4]=2$ 可以發現 $dp[1]$ 和 $dp[2]$ 都是 $(dp[4]-1)=1$ 但只有 $A_2=3$ 比 $A_4=4$ 小 因此在真正的 $LIS$ 中， $A_3$ 就可以接在 $A_2$ 後面 --- ## 刷題時間 ---- 很多 $LIS$ 的題目都是難在看不出他是 $LIS$ 只要看出來通常就可以快樂 AC 啦~ ---- [2021/1 APCS p4 飛黃騰達](https://zerojudge.tw/ShowProblem?problemid=f608) [UVa 00481 What Goes Up](https://zerojudge.tw/ShowProblem?problemid=d242) [2021 TOI 入營考 pC 粉刷護欄](https://tioj.ck.tp.edu.tw/problems/2195) [UVa 11456 Trainsorting](https://zerojudge.tw/ShowProblem?problemid=d052)