理论：动态规划初步--最长上升子序列(LIS)
模板：

void slove()
{
    fill(dp, dp + n, INF);
    for (int i = 0; i < n; i++)
    {
        *lower_bound(dp, dp + n, a[i]) = a[i];
        // *upper_bound(dp, dp + n, a[i]) = a[i];  // 非严格递增用upper_bound
    }
    int first = lower_bound(dp, dp + n, INF) - dp;
    printf("%d\n", dp[first - 1]);
    printf("%d\n", first);
}

LC 1713. 得到子序列的最少操作次数

题解：相当于求最长公共子序列，但是普通的算法需要O(n*m)。
这道题目target数组是互异的，可以给它从1开始编号，拿这个编号规则再给arr编号。这样target已经是升序了，arr的LIS也就是原数组的最长公共子序列。

const int INF = 0x3f3f3f3f;
class Solution {
public:
    int minOperations(vector<int>& target, vector<int>& arr) {
        unordered_map<int, int>mp;
        int cnt = 0;
        for(int num : target) mp[num] = (++cnt);
        vector<int>myarr;
        for(int& num : arr) {
            if(mp[num])  myarr.push_back(mp[num]);
        }
        int n = arr.size();
        vector<int>dp(n, INF);
        for(int num : myarr) {
            *lower_bound(dp.begin(), dp.end(), num) = num;
        }
        int lis = lower_bound(dp.begin(), dp.end(), INF)-dp.begin();
        return target.size() - lis;
    }
};