三十分求助
查看原帖
三十分求助
978486
ca0vnv楼主2024/8/17 20:01

三十分求助

#include<bits/stdc++.h>
using namespace std;
const int N = 5e5 + 10;
int a[N], cnt, f[N], b[N];
int LIS(int n)
{
    int ans = 1, len = 0;
    for (int i = 1; i <= cnt; i++)
    {
        f[i] = 1;
    }
    b[++len] = a[1];
    for (int i = 2; i <= n; i++)
    {
        if (a[i] < b[len])
        {
            b[++len] = a[i];
        }
        else
        {
            *upper_bound(b + 1, b + 1 + len, a[i], greater<int>()) = a[i];
        }
    }
    return len;
}
int main(){
    int x,n;
    cin>>n;
    for (int i = 1; i <= n; i++)
    {
        cin>>x;
        a[++cnt]=x;
    }
    cout<<LIS(cnt)<<endl;
    system("Pause>Nul");
    return 0;
}
2024/8/17 20:01
加载中...