# Longest Increasing Subsequence (LIS) 最長遞增子序列
最長遞增子序列是什麼？
就是字面上的意思
沒什麼好說的
舉個栗子🌰
[3 5 2 3 7]這個數列中的最長遞增序列為[2 3 7]
用眼睛看一下就能出來
但是要怎麼有效的找出來呢？

用上面的例子說明如何找出最長遞增子序列的長度:



### CSES:Increasing Subsequence
https://cses.fi/problemset/task/1145

#include<bits/stdc++.h>
using namespace std;
#define int long long
#define endl '\n'
#define inf 2e18
#define maxn 100005
#define mod 1000000007


signed main(){

    ios::sync_with_stdio(0);
    cin.tie(0);

    int n;
    cin>>n;
    vector<int>vec(n+1);    //從1開始數
    for(int i=1;i<=n;i++){
        cin>>vec[i];
    }
    vector<int>lis;
    lis.push_back(vec[1]);    //把第一項直接放進去Lis中，如上圖步驟1
    for(int i=2;i<=n;i++){    //從第二項一路走到最後一項
        if(vec[i]>*lis.rbegin()){//如果此數大於Lis中的最後一項(當前Lis中最大的數)，
            lis.push_back(vec[i]);//則直接將此數加入Lis的最後一項，如上圖步驟2及步驟7
        }
        else{//否則找到第一個大於此數的數並且將其替換掉，如步驟4及步驟6
            *lower_bound(lis.begin(),lis.end(),vec[i])=vec[i];
        }
    }
    cout<<lis.size();
}