题目描述

有长度为N的序列:
A1 A2 …..An
求最长不下降子序列：Ai1,Ai2,,,,,Aik, 其中ai1<=ai2<=…..<=aik
求最长不下降子序列的长度

输入

11

1 3 6 3 4 7 5 7 6 7 8

输出

8

思路

每次把当前数替换掉最小的比当前数大的数，记录下当前的长度，和max进行判断就可以了

#include
using namespace std;
int a[1000],d[1000];
int ef(int f,int k)
{
    int l=1,r=k,mid;
    while(l<=r)
    {
        mid=(l+r)/2;
        if(d[mid]==f)   return mid;
        if(d[mid]f)    r=mid-1;
    }
    return l;
}
int main()
{
    int n,c,len;
    scanf("%d",&n);
    for (int i=1;i<=n;++i)
        scanf("%d",&a[i]);
    d[1]=a[1];
    len=1;
    for (int i=1;i<=n;++i)
    {
        c=ef(a[i],len);
        d[c]=a[i];
        if(c>len)   len=c;
    }
    printf("%d",len);

}