最长单一递减子序列 采用二分搜索算法，时间复杂度O(nlgn)

最长单调递减子序列 采用二分搜索算法，时间复杂度O(nlgn)。

int LIS(int a[], int n)
{
 int i=0, k;
 int l, h;
 int *b=new int[n+1];
 b[1]=a[0];
 for(i=1, k=1; i<n; i++)
 {
  if(a[i]<b[k])
   b[++k]=a[i];
  else
  {//更新b[]
   if(a[i]>b[1])
    b[1]=a[i];
   else
   {//二分查找
    for(l=1, h=k; l!=h-1; )
    {
     int mid=(l+h)/2;
     if(b[mid]<=a[i])
      h=mid;
     else
      l=mid;
    }
    b[h]=a[i];
   }
  }
 }

 return k;
}

int main()
{
 int a[]={9,4,3,2,5,4,3,2};
 cout<<LIS(a, 8)<<endl;
 
}