这篇文章上次修改于 909 天前，可能其部分内容已经发生变化，如有疑问可询问作者。

本文共 411 个字，阅读时长 ≈ 2 分钟

AcWing 895. 最长上升子序列

这个要报算法基础课才有所以不放链接了，洛谷上类似的有导弹拦截。

闫氏DP分析法 算了我没学会

有$n$个整数，求最长上升子序列。

从$1$到$n$遍历，设每一个下标为一个最长上升子序列的终点，从$1$到这个下标遍历，如果满足上升就比较一下，看当前已经找到的最长的长度是否比这个再加上终点本身的长度长，如果是就更新。

#include<iostream>
using namespace std;
int a[1003],f[1003];
int main()
{
    int n,ans=0;
    cin>>n;
    for(int i=1;i<=n;++i) cin>>a[i];
    for(int i=1;i<=n;++i){
        f[i]=1;
        for(int j=1;j<i;++j){
            if(a[j]<a[i]) f[i]=max(f[i],f[j]+1);
        }
        ans=max(ans,f[i]);
    }
    cout<<ans<<endl;
    return 0;
}