LIS(最長遞增子序列)

簡介

LIS是要計算一個序列中最長的遞增子序列，例如
[10, 9, 2, 5, 3, 7, 101, 18]
這個序列中的最長遞增子序列可以是[2, 3, 7, 101]，LIS的答案可以不為一，可能有很多種答案，因此我們要求的是他的最長長度。而我將會介紹

O (N^{2})

和

O (N l o g N)

的做法!

$O (N^{2})$ 的作法

我們可以直接窮舉先前每項數字的LIS，並去計算哪一種的長度最長。
定義

d p [i]

表示以

i

為結尾的最長遞增子序列。
因此要計算

d p [i]

需要去檢查小於

i

的所有位置，假設

j

是我們要去檢查的位置，如果

j < i

並且

a r r [j] > a r r [i]

則可以把

a r r_{j}

為結尾的LIS接上來，最長遞增子序列的值就會變成

d p [j] + 1

，當然啦我們是要求最長的，所以即使有非常多種答案，我們最終要取最好的，因此我們可以得到轉移式

$d p [i] = m a x (d p [j] + 1, d p [i]) i f j < i & & a r r [j] < a r r [i]$

$O (N^{2})$ code
























#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題（題目）就是LIS的裸題，可以去練習看看。

leetcode 300. Longest Increasing Subsequence參考解答
















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;
    }
};

那接下來做做看這一題CSES 1145: Increasing Subsequence，當你很開心的寫下下面這個code

CSES 1145: Increasing Subsequence






























#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 \leq n \leq 2 \cdot 10^{5}

，顯然

O (N^{2})

不會過，因此我要來介紹

O (N l o g N)

的解法

$O (N l o g N)$

接下來要介紹

O (N l o g N)

的作法，

O (N l o g N)

的做法我會兩種，一種是用二分搜去優化，另一種是使用資料結構做優化。

二分搜優化

這個作法是利用二分搜去優化。
首先我們先用

a r r []

讀入測資，接著創建一個vector，稱作

v []

好了，存儲目前為止找到的最長遞增子序列，我們要利用

v [j]

紀錄第

j

個位子的最小值，也就是說

v [j]

是要紀錄在

j

的時候最小的

a r r

，並更有潛力的建構出LIS。接著再利用二分搜去更新我們的

v [j]

。
我拿上面那個例子示範一次，arr = [10, 9, 2, 5, 3, 7, 101, 18]。

一開始我們將
$10$ 推進
$v$ 裡面，此時v={10}
再來尋找
$9$ 在
$v$ 的位置，可以發現
$9$ 小於
$10$ ，因此
$10$ 替換成
$9$ ，此時v={9}
$2$ 小於
$9$ ，因此
$9$ 替換成
$2$ ，此時v={2}
處理
$5$ ，由於
$5$ 大於
$2$ ，所以把
$5$ 推進
$v$ ，此時v={2, 5}
接著
$3$ 小於
$5$ ，因此
$5$ 替換成
$3$ ，此時v={2, 3}
處理
$7$ ，由於
$7$ 大於
$3$ ，所以把
$7$ 推進
$v$ ，此時v={2, 3, 7}
$101$ 大於
$7$ ，所以把
$101$ 推進
$v$ ，此時v={2, 3, 7, 101}
$18$ 小於
$101$ ，因此
$101$ 替換成
$18$ ，此時v={2, 3, 7, 18}
完成

在建構LIS的過程中可以發現

v

裡面的數字具有單調性，因此在尋找的時候可以使用二分搜。

leetcode 300. Longest Increasing Subsequence參考解答













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 (l o g N)

的時間做查詢(query)，和

O (l o g N)

的時間做更新(update)，利用這個特性可以在

O (N l o g N)

下找出LIS。
首先定義

d p [i]

是區間

[0, i]

的LIS長度，接著列出轉移式:

d p [i] = m a x (d p [1], d p [2], d p [3], . . . ., d p [i - 1]) + 1

會發現

m a x (d p [1], d p [2], d p [3], . . . ., d p [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)，
$d p [10] = 1$ 。
處理第二個元素，查詢BIT，找到比9小的位置中最大的LIS長度：query(9 - 1) = 0，並將這個回傳值加上1，更新BIT和答案：update(9, 1)，
$d p [9] = 1$ 。
處理第三個元素，查詢BIT，找到比2小的位置中最大的LIS長度：query(2 - 1) = 0，並將這個回傳值加上1，更新BIT和答案：update(2, 1)，
$d p [2] = 1$ 。
處理第四個元素，查詢BIT，找到比5小的位置中最大的LIS長度：query(5 - 1) = 1，並將這個回傳值加上1，更新BIT和答案：update(5, 1)，
$d p [10] = 2$ 。
以此類推，最後可以計算到LIS為4。

那一樣我先放上LeetCode的那一題的參考做法





































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;
    }
};

再來就是我們的重頭戲了CSES 1145: Increasing Subsequence的

O (N l o g N)

的做法

CSES 1145: Increasing Subsequence optimized by BIT















































#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 \leq n \leq 2 \cdot 10^{5}

，

1 \leq x_{i} \leq 10^{9}

，由於是對值域做查詢和更新，按照題目的限制

1 \leq x_{i} \leq 10^{9}

陣列會爆，因此要先做離散化，做完離散化之後就按照上面的步驟處理，最後找尋

m a x (d p [1], d p [2], d p [3], . . . ., d p [N])

就是我們的答案了!

優化後的做法真的好神奇好美妙喔，希望大家都能一起欣賞這個優化的美，太喜歡了~~~
太開心了我寫完這篇LIS的介紹了!

LIS(最長遞增子序列)

簡介

O(N2)的作法

O(N2) code

O(NlogN)

二分搜優化

資料結構優化

Reference

Read more

Codebook

information security hw3

OS hw1

TSMC Hackathon

$O (N^{2})$ 的作法

$O (N^{2})$ code

$O (N l o g N)$