# longest common subsequence 優化

:::success
基礎LIS作法只有$O(n^2)$，但利用patience sorting & bit可以到O(nlogn)
:::

patience sorting
--
* 假設有一撲克牌序列，以及一個存放處理完的撲克牌的地方
* **規則**：
1. 每次取一張
2. 從最左邊的一疊開始，如果那一疊牌的最上方比目前拿的牌還小，那就再往左邊一疊看，直到最上方的牌比目前還大，就疊上去。否則找不到的話就建立新的一疊。
* 示意：

順序：

> source:https://www.cs.princeton.edu/courses/archive/spring13/cos423/lectures/LongestIncreasingSubsequence.pdf

lis
--
* 利用patience sort, lis即為撲克牌的疊數，如上圖是5。
* 原因：
* 在第n疊牌中，每個第0~n-1疊中一定有一張（不一定是最上層）是比第n疊其中最上層還小。因為就規則而言，只要比最上層大，那就要往右邊走，所以就算之後在第n-1疊中加入比第n疊的最上層還大的牌，n-1中的第二張還是比較小。
* 而每一次把一張牌疊上去，可以視為把標準拉低，因為發現有比目前最上層還小的牌，所以更容易讓lis增大。

程式碼：

#include <bits/stdc++.h>

using namespace std;

int main(){
    ios_base::sync_with_stdio(false);
    cin.tie(0);
    int n;
    cin >> n;

    vector<int> val(n);
    for(int i=0;i<n;++i) cin >> val[i];

    vector<int> cur;
    cur.push_back(val[0]);

    for(int i=1;i<n;++i){
        if(val[i]>cur.back())
            cur.push_back(val[i]);
        else
            *lower_bound(cur.begin(), cur.end(), val[i])=val[i];
    }

    cout << cur.size() << "\n";
}