最长上升子序列

最长上升子序列

两道模板题，体验时间复杂度带来的快感以及方法不同的乐感！

AcWing 895. 最长上升子序列

AcWing 896. 最长上升子序列 II

895. 最长上升子序列 - AcWing题库

我们用a[i]表示原序列，f[i]是记录这个数的值是多少！ 

而后递推一下子就出来了

对于不懂如何递推的话请看下图：

 

 可以自己模拟一下

代码中的f[i] = 1是指我把f[ ]里里面的值全设为1

#include
#include
#include
#include
using namespace std;
const int N = 1020;
int a[N],f[N];
int n;
int main()
{
    int ans = 1;
    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[i] > a[j])f[i] = max(f[i],f[j]+1);
        ans = max(ans,f[i]);
    }
    cout<
    return 0;
}

  Ps:学东西要学透不是吗

我们想想上面这个dp状态的时间复杂度为 O(n ^ 2)时间开销是不是很大？

于是我们得想另外的办法降低时间复杂度对吧

二分查找方法

二分查找的时间复杂度是O(nlogn)所以对于数据大一点的来讲，这个方法不会出错！！

例题请看：

896. 最长上升子序列 II - AcWing题库

数据范围变了一下而已 

#include
#include
#include
using namespace std;
const int N = 1e5+10;
int n;
int a[N],f[N];//f[]记录上升子序列,表示有序数列
int len;//上升子序列的长度
int find(int x)//二分查找第一个大于等于x的位置 
{
    int l = 1,r = len,mid;
    while(l <= r)
    {
        mid = (l+r)>>1;
        if(x > f[mid]) l = mid+1;
        else r = mid-1;
    }
    return l;
}
//也不是不可以用lower_bound( )
int main()
{
    cin>>n;
    int j;
    len = 1;
    for(int i = 1;i <= n;i++)cin>>a[i];
    f[1] = a[1];
    
    //考虑新加进来的a[i]
    for(int i = 2;i <= n;i++)
    {
        //大于则添加
        if(a[i] > f[len]) f[++len] = a[i];
    
    else//小于等于则替换 
    {
        j = find(a[i]);
        f[j] = a[i];
    }
    }
    cout<
 
    return 0;
}