最长上升子序(lis)

最长上升子序 通常 有两种写法

第一种 就是 朴素求法 时间复杂度为O(n²)
        用 朴素求法 时,数据稍微 好一点,都会超时 所以 一般不会用它 去做题
进入正题 :
          第二种求法 则将时间复杂度优化到O(nlogn)

#include<cstdio>
#include<cstring>
#include<algorithm>

using namespace std;

int a[100005];  
int lis[100005];     //用来存  上升 序列 

int main()
{
   
    int n;
    int count = 1;
    scanf( "%d",&n);

    memset(a,0,sizeof(a));
    memset(lis,0,sizeof(lis));

    for(int i = 1;i <= n;i++)  scanf("%d",&a[i]);
   
    lis[count] = a[1];    //将 第一个数 存进 s 数组                                                                                                                                                                
    // 因为 每操作 一次 的结果都是 最长 且 最小 的子序列,所以 是不会漏掉 任何一个数的
    for(int i = 2;i <= n;i++) // 第一个数已经判断过
    {
      
        if(a[i] > lis[count])    //如果a[i]  > lis 的最后一个数字,就将 a[i] 存进 lis 数组
        {
        //如果要求 最长 不下降子序  则 将 这里  >  换成 >= 即可
                count++;
                lis[count] = a[i];
        }
        else     
        {
                                                                    //lower_bound   内部是用 二分 实现的
            int temp = lower_bound(lis + 1,lis + count + 1,a[i]) - lis;//  在lis中  找到 第一个大于等于a[i]的   地址
            lis[temp] = a[i];      // 将 找到的这个数  替换为 a[i]  
        }
                //所以最后  lis 数组存放的也就是 最长 且 最小 的上升子序列
    }   

    printf("%d\n",count);

    return 0;
}