最长上升子序列

//f(x)代表以a(x)结尾的最长上升子序列的长度
//当a[p]<a[x]时，f[x]可以用f[p]+1表示

优化前

运行超时

#include<iostream>
#include<cstdio>
using namespace std;
const int N=100005;
int n;
int a[N],f[N];//a[i]结尾
int main()
{
    scanf("%d",&n);
    for(int i=1;i<=n;i++)scanf("%d",&a[i]);
    int maxv=0;
    for(int i=1;i<=n;i++)
    {
        f[i]=1;
        for(int k=1;k<i;k++)
        {
            if(a[k]<a[i])f[i]=max(f[i],f[k]+1);
        }
    }
    int res=0;
    for(int i=1;i<=n;i++)res=max(res,f[i]);
    printf("%d\n",res);
    return 0;
}

deepseek给出的解法

可以通过测试点

#include<iostream>
#include<vector>
#include<algorithm>
using namespace std;

int main() {
    int n;
    scanf("%d", &n);
    vector<int> a(n);
    for (int i = 0; i < n; i++) {
        scanf("%d", &a[i]);
    }

    vector<int> dp;
    for (int i = 0; i < n; i++) {
        auto it = lower_bound(dp.begin(), dp.end(), a[i]);
        if (it == dp.end()) {
            dp.push_back(a[i]);
        } else {
            *it = a[i];
        }
    }

    printf("%d\n", dp.size());
    return 0;
}

代码解释：
dp 数组：dp[i] 表示长度为 i+1 的最长上升子序列的最后一个元素的最小值。

lower_bound：使用 lower_bound 函数在 dp 数组中找到第一个大于等于 a[i] 的元素的位置。如果找不到这样的元素，说明 a[i] 可以扩展当前的最长上升子序列，因此将其添加到 dp 数组的末尾。否则，更新 dp 数组中对应位置的元素为 a[i]。

最终结果：dp 数组的长度就是最长上升子序列的长度。

时间复杂度：
每次使用 lower_bound 的时间复杂度是 O(logn)，因此总的时间复杂度是 O(nlogn)。