C++ 代码

//维护数组f，每处理一个数字，更新一次f
//f[i]表示当前已处理数字序列的长度为i的上升子序列中的最小结尾数字
//当处理完所有数字后，f大小即为LIS的大小
//对当前待处理数字a[i]，若a[i]大于f中的所有数，则push_back(a[i])，
//否则，二分查找到第一个大于等于a[i]的数f[l],f[l]=a[i]
//因为f[l]之前的数都小于a[i]，a[i]可以加在其对应的子序列之后，使子序列长度+1，
//于是长度为l-1的子序列们尾后加上a[i]，
//组成了长度为l且最小结尾数小于之前的f[l]的子序列
//根据f定义，故替f[l]为a[i]
#include<bits/stdc++.h>
using namespace std;
const int N = 1e5 + 10;
int a[N], n;
vector<int> f;
int main()
{
    cin >> n;
    for (int i = 1; i <= n; i++) cin >> a[i];
    for (int i = 1; i <= n; i++)
    {
        auto t = lower_bound(f.begin(), f.end(),a[i]);
        if (t == f.end())
            f.push_back(a[i]);
        else *t = a[i];
    }
    cout << f.size();
    return 0;
}