nyoj214——单调递增子序列(二)

给定一整型数列{a₁,a₂...,a_n}（0<n<=100000），找出单调递增最长子序列，并求出其长度。

如：1 9 10 5 11 2 13的最长单调递增子序列是1 9 10 11 13，长度为5。

71 9 10 5 11 2 1322 -1样例输出
51
解决方法：复杂度为O(nlogn)的求最长递增子序列
#include <iostream>#include <cstdio>#include <cstring>#include <climits>#define maxn 100005using namespace std;int dp[maxn],a[maxn];int Search(int x,int len){    int left=1,right=len,mid=(left+right)>>1;    while(left<=right)    {        if(x>dp[mid])        {            left=mid+1;        }        else        {            if(x==dp[mid])                return mid;            else            {                right=mid-1;            }        }        mid=(left+right)>>1;    }    return left;}int main(){    int n;    while(~scanf("%d",&n))    {        for(int j=0;j<n;j++)            scanf("%d",&a[j]);        int cnt=1;        dp[0]=-INT_MAX;        dp[1]=a[0];        for(int j=1;j<n;j++)        {            int pos=Search(a[j],cnt);//            dp[pos]=a[j];            if(pos>cnt)                cnt=pos;        }        PRintf("%d/n",cnt);    }    return 0;}