其实解释POJ 2533 原题

最长上升子序列，用O(N*N)算法和o(n*logn)算法分别实现，学校OJ的数据比较弱，就算写成最长不下降子序列也可以通过，但是在POJ上是WA的

而题意本身应该是严格递增的

 

o(N*N)

#include 
     
      #include 
      
       #define N 10010int a[N];int n;void LOS(){    int dp[N],i,j,tmp,max;    memset(dp,0,sizeof(dp));    dp[1]=1; max=1;    for(i=2; i<=n; i++)    {        for(tmp=0,j=1; j
       
        a[j] && dp[j]>tmp)                tmp=dp[j];        dp[i]=tmp+1;        if(dp[i]>max) max=dp[i];    }    printf("%d\n",max);}int main(){    int i;    while(scanf("%d",&n)!=EOF && n)    {        for(i=1; i<=n; i++) scanf("%d",&a[i]);        LOS();    }    return 0;}
       
      
     

 

 

 

O(n*logn)

#include 
     
      #include 
      
       #define N 1010int a[N],c[N],n;int binary_search(int key , int l , int r){    int mid;    while(l<=r)    {        mid=(l+r)/2;        if(c[mid]
       
        c[top]) c[++top]=a[i];        else        {            x=binary_search(a[i],1,top);            c[x]=a[i];        }    }    printf("%d\n",top);}int main(){    int i;    while(scanf("%d",&n)!=EOF && n)    {        for(i=1; i<=n; i++) scanf("%d",&a[i]);        LOS();    }    return 0;}