最大上升子序列

思路：

建立一个low数组，用于存放上升的子序列，并记录长度，如果一个数大于low的最后一个数，则将他添加到low数组最后面，如果不大于，则将那个数利用二分放在low合适的位置，以便下次比较。

时间复杂度O(nlogn)

Code：

#include<iostream>
#include<algorithm>
#include<cmath>
using namespace std;
const int N=1e6+5;
int n,len;//n为a数组的长度，len为low数组的长度
int a[N],low[N];
int find(int x)
{
    int l=1,r=len;
    while(l<=r)//二分查找
    {
        int mid=(l+r)>>1;
        if(x>=low[mid]) l=mid+1;
        else r=mid-1;
    }
    return l;
}
void lis()
{
    low[1]=a[1];//默认第一个数是上升的
    len=1;//此时low的长度为1
    for(int i=2;i<=n;i++)
    {
        if(a[i]>low[len])//判断当前数是不是大于low数组中最后的数 
        {
            low[++len]=a[i];//如果大于，则将他添加到low数组中 长度自增1
        }
        else
        {
            low[find(a[i])]=a[i];//如果小于 则更新low数组
        }
    }    
}
int main()
{
    cin>>n;
    for(int i=1;i<=n;i++)
    {
        cin>>a[i];
        low[i]=989898;//给low数组赋最大值
    }
    lis();
    cout<<len<<endl;
    return 0;
}