# LIS(最長遞增子序列)
## 簡介
LIS是要計算一個序列中最長的遞增子序列，例如
`[10, 9, 2, 5, 3, 7, 101, 18]`
這個序列中的最長遞增子序列可以是`[2, 3, 7, 101]`，LIS的答案可以不為一，可能有很多種答案，因此我們要求的是他的最長長度。而我將會介紹$O(N^2)$和$O(NlogN)$的做法!
## $O(N^2)$的作法
我們可以直接窮舉先前每項數字的LIS，並去計算哪一種的長度最長。
定義 $dp[i]$ 表示以$i$為結尾的最長遞增子序列。
因此要計算 $dp[i]$ 需要去檢查小於$i$的所有位置，假設$j$是我們要去檢查的位置，如果 $j < i$ 並且 $arr[j] > arr[i]$ 則可以把 $arr_j$ 為結尾的LIS接上來，最長遞增子序列的值就會變成 $dp[j] + 1$，當然啦我們是要求最長的，所以即使有非常多種答案，我們最終要取最好的，因此我們可以得到轉移式
- $dp[i] = max(dp[j] + 1, dp[i])\qquad if\quad j < i \quad \&\& \quad arr[j] < arr[i]$
### $O(N^2)$ code
```cpp=
#include <bits/stdc++.h>
#define IOS ios_base::sync_with_stdio(false);cin.tie(0);cout.tie(0);
using namespace std;
typedef long long ll;
int main(){
IOS
int arr[100];
int n;
cin >> n;
for(int i = 0;i < n;i++) cin >> arr[i];
int dp[100];
for(int i = 0;i < n;i++) dp[i] = 1;
for(int i = 0;i < n;i++){
for(int j = 0;j < i;j++){
if(arr[i] > arr[j])
dp[i] = max(dp[j] + 1, dp[i]);
}
}
int ans = 1;
for(int i = 0;i < n;i++) ans = max(ans, dp[i]);
cout << ans << '\n';
return 0;
}
```
那在leetcode的300題（<a href="https://leetcode.com/problems/longest-increasing-subsequence/description/">題目</a>）就是LIS的裸題，可以去練習看看。
:::spoiler leetcode 300. Longest Increasing Subsequence參考解答
```cpp=
class Solution {
public:
int lengthOfLIS(vector<int>& nums) {
int dp[3000];
for(int i = 0;i < nums.size();i++) dp[i] = 1;
for(int i = 0;i < nums.size();i++){
for(int j = 0;j < i;j++){
if(nums[i] > nums[j])
dp[i] = max(dp[j] + 1, dp[i]);
}
}
int ans = 1;
for(int i = 0;i < nums.size();i++) ans = max(ans, dp[i]);
return ans;
}
};
```
:::
<hr>
那接下來做做看這一題<a href="https://cses.fi/problemset/task/1145/">CSES 1145: Increasing Subsequence</a>，當你很開心的寫下下面這個code
:::spoiler CSES 1145: Increasing Subsequence
```cpp=
#include <bits/stdc++.h>
#include <ext/pb_ds/assoc_container.hpp>
#include <ext/pb_ds/tree_policy.hpp>
#define IOS ios_base::sync_with_stdio(false);cin.tie(0);cout.tie(0);
#define INF 0x3f3f3f3f
#define int long long
#define lowbit(x) x&(-x)
using namespace std;
using namespace __gnu_pbds;
typedef long long ll;
const int N = 2e5 + 5;
int n, dp[N], arr[N];
signed main(){
IOS
cin >> n;
for(int i = 0;i < n;i++)
cin >> arr[i];
for(int i = 0;i < n;i++) dp[i] = 1;
for(int i = 0;i < n;i++){
for(int j = 0;j < i;j++){
if(arr[i] > arr[j])
dp[i] = max(dp[i], dp[j] + 1);
}
}
int ans = 1;
for(int i = 0;i < n;i++) ans = max(ans, dp[i]);
cout << ans << '\n';
return 0;
}
```
:::
發現竟然吃了TLE，可以看到這一題的限制是$1≤n≤2⋅10^5$，顯然$O(N^2)$不會過，因此我要來介紹$O(NlogN)$的解法
## $O(NlogN)$
接下來要介紹$O(NlogN)$的作法，$O(NlogN)$的做法我會兩種，一種是用二分搜去優化，另一種是使用資料結構做優化。
### 二分搜優化
這個作法是利用二分搜去優化。
首先我們先用$arr[]$讀入測資，接著創建一個vector，稱作$v[]$好了，存儲目前為止找到的最長遞增子序列，我們要利用$v[j]$紀錄第$j$個位子的最小值，也就是說$v[j]$是要紀錄在$j$的時候最小的$arr$，並更有潛力的建構出LIS。接著再利用二分搜去更新我們的$v[j]$。
我拿上面那個例子示範一次，`arr = [10, 9, 2, 5, 3, 7, 101, 18]`。
1. 一開始我們將$10$推進$v$裡面，此時`v={10}`
2. 再來尋找$9$在$v$的位置，可以發現$9$小於$10$，因此$10$替換成$9$，此時`v={9}`
3. $2$小於$9$，因此$9$替換成$2$，此時`v={2}`
4. 處理$5$，由於$5$大於$2$，所以把$5$推進$v$，此時`v={2, 5}`
5. 接著$3$小於$5$，因此$5$替換成$3$，此時`v={2, 3}`
6. 處理$7$，由於$7$大於$3$，所以把$7$推進$v$，此時`v={2, 3, 7}`
7. $101$大於$7$，所以把$101$推進$v$，此時`v={2, 3, 7, 101}`
8. $18$小於$101$，因此$101$替換成$18$，此時`v={2, 3, 7, 18}`
9. 完成
在建構LIS的過程中可以發現$v$裡面的數字具有單調性，因此在尋找的時候可以使用二分搜。
:::spoiler leetcode 300. Longest Increasing Subsequence參考解答
```cpp=
class Solution {
public:
int lengthOfLIS(vector<int>& nums) {
vector<int> v;
int n = nums.size();
for(int i = 0;i < n;i++){
int p = lower_bound(v.begin(), v.end(), nums[i]) - v.begin();
if(p == v.size()) v.push_back(nums[i]);
else v[p] = nums[i];
}
return v.size();
}
};
```
:::
那用這個方法解CSES那一題就留給大家做做看，因為那一題我想用下一個做法示範一下，嘿嘿。
### 資料結構優化
在這個方法中我使用BIT(Binary Indexed Tree)來做優化，BIT通常是處理區間問題，BIT可以用$O(logN)$的時間做查詢(query)，和$O(logN)$的時間做更新(update)，利用這個特性可以在$O(NlogN)$下找出LIS。
首先定義$dp[i]$是區間$[0, i]$的LIS長度，接著列出轉移式:
$$dp[i] = max(dp[1], dp[2], dp[3], ...., dp[i - 1]) + 1$$
會發現$max(dp[1], dp[2], dp[3], ...., dp[i - 1]) + 1$其實在求的是前綴最大值，發現到這間件事情之後便可以巧妙的利用BIT去優化。
這邊我們BIT是要對值域做更新和查詢，記得是「值域」喔，所以每一次做更新的時候我們要先找比該元素小1的值做查詢，查看比該元素小的LIS長度是多少，同樣使用這個例子`[10, 9, 2, 5, 3, 7, 101, 18]`。
- 處理第一個元素，查詢BIT，找到比10小的位置中最大的LIS長度：query(10 - 1) = 0，並將這個回傳值加上1，更新BIT和答案：update(10, 1)，$dp[10]=1$。
- 處理第二個元素，查詢BIT，找到比9小的位置中最大的LIS長度：query(9 - 1) = 0，並將這個回傳值加上1，更新BIT和答案：update(9, 1)，$dp[9]=1$。
- 處理第三個元素，查詢BIT，找到比2小的位置中最大的LIS長度：query(2 - 1) = 0，並將這個回傳值加上1，更新BIT和答案：update(2, 1)，$dp[2]=1$。
- 處理第四個元素，查詢BIT，找到比5小的位置中最大的LIS長度：query(5 - 1) = 1，並將這個回傳值加上1，更新BIT和答案：update(5, 1)，$dp[10]=2$。
- 以此類推，最後可以計算到LIS為4。
那一樣我先放上LeetCode的那一題的參考做法
```cpp=
class Solution {
public:
const static int N = 3000;
vector<int> b;
int arr[N + 5], dp[N + 5];
int lowbit(int x){
return x&(-x);
}
int query(int idx){
int ans = 0;
for(int i = idx;i > 0;i-=lowbit(i)){
ans = max(dp[i], ans);
}
return ans;
}
void update(int idx, int val){
for(int i = idx;i <= N;i+=lowbit(i)){
dp[i] = max(dp[i], val);
}
}
int lengthOfLIS(vector<int>& nums) {
int n = nums.size();
for(int i = 0;i < n;i++) b.push_back(nums[i]);
sort(b.begin(), b.end());
b.resize(unique(b.begin(), b.end()) - b.begin());
for(int i = 0;i < n;i++)
nums[i] = lower_bound(b.begin(), b.end(), nums[i]) - b.begin() + 1;
for(int i = 0;i <= N;i++) dp[i] = 0;
for(int i = 0;i < n;i++){
int leng = query(nums[i] - 1) + 1;
update(nums[i], leng);
}
int ans = 1;
for(int i = 0;i <= N;i++) ans = max(ans, dp[i]);
return ans;
}
};
```
<hr>
再來就是我們的重頭戲了CSES 1145: Increasing Subsequence的$O(NlogN)$的做法
:::spoiler CSES 1145: Increasing Subsequence optimized by BIT
```cpp=
#include <bits/stdc++.h>
#include <ext/pb_ds/assoc_container.hpp>
#include <ext/pb_ds/tree_policy.hpp>
#define IOS ios_base::sync_with_stdio(false);cin.tie(0);cout.tie(0);
#define INF 0x3f3f3f3f
#define int long long
#define lowbit(x) x&(-x)
using namespace std;
using namespace __gnu_pbds;
typedef long long ll;
const int N = 2e5 + 5;
vector<int> b;
int arr[N + 5], dp[N + 5], lis = 1, n;
int query(int idx){
int ans = 0;
for(int i = idx;i > 0;i-=lowbit(i)){
ans = max(dp[i], ans);
}
return ans;
}
void update(int idx, int val){
for(int i = idx;i <= N;i+=lowbit(i)){
dp[i] = max(dp[i], val);
}
}
signed main(){
IOS
cin >> n;
for(int i = 1;i <= n;i++){
cin >> arr[i];
b.push_back(arr[i]);
}
sort(b.begin(), b.end());
b.resize(unique(b.begin(), b.end()) - b.begin());
for(int i = 1;i <= n;i++)
arr[i] = lower_bound(b.begin(), b.end(), arr[i]) - b.begin() + 1;
for(int i = 0;i <= N;i++) dp[i] = 0;
for(int i = 1;i <= n;i++){
int leng = query(arr[i] - 1) + 1;
update(arr[i], leng);
}
int ans = 1;
for(int i = 0;i <= N;i++) ans = max(ans, dp[i]);
cout << ans << '\n';
return 0;
}
```
:::
我稍微講一下這一題，Constraints是$1≤n≤2⋅10^5$，$1≤x_i≤10^9$，由於是對值域做查詢和更新，按照題目的限制$1≤x_i≤10^9$陣列會爆，因此要先做離散化，做完離散化之後就按照上面的步驟處理，最後找尋$max(dp[1], dp[2], dp[3], ...., dp[N])$就是我們的答案了!
優化後的做法真的好神奇好美妙喔，希望大家都能一起欣賞這個優化的美，太喜歡了~~~
太開心了我寫完這篇LIS的介紹了!
## Reference
- https://yuihuang.com/dp-lis/
- https://www.csie.ntu.edu.tw/~sprout/algo2021/homework/hand10.pdf
Sign in with Wallet
Connect another wallet