看了别人的解题报告后写的~
不然让我想破头皮也想不出为什么要这样做!~

虽然AC 但让我很疑惑~

技巧：设置一个数组a[i]

存放所有长度为i的上升子序列中最小的末元素值，比如说只有两个长度为3的上升子序列123和124，那么a[3]中存放的就是3（末元素3<4）

那么当来一个新数data时，如果它的值大于最长长度的末元素的值（即a[ans]），则ans++；且a[ans]=data;

否则，通过二分查找（数组a中的元素为递增），将最接近data且大于data的那个元素更新为data，既最小的大于它的数。
例如1,5,3,4,之后来个2，a[1]=1,a[2]=3,a[3]=4;则更新a[2]=2;
由于二分查找复杂度为log(n)，外围为n,总的复杂度为nlogn





其中测试数据
9
5 8 9 2 3 1 7 4 6
按照上面的方法的话应该是1 3 4 6   答案是 4
但是仔细想1 3 4 6 不应该是正解,应该是 2 3 4 6
哪位大牛告诉我这是为何?~~

ft!

附AC 的代码~

Problem: 1631  User: 810974380 
Memory: 320K  Time: 110MS 
Language: C++  Result: Accepted 

Source Code 
#include<stdio.h>
#include<stdlib.h>
int list[40000]; 
int t,n,num,res,i,w;
int binary_search(int left,int right,int path)
{ int mid;
   while(left<=right)
   {
      mid=(left+right)/2;
      if(list[mid]<path) left=mid+1;
      else  right=mid-1;
   }
  return right;//输出大于等于num的最小的数的位置 
}
int main()
{   
  scanf("%d",&t);
  while(t--)
  {
     scanf("%d",&n);
     scanf("%d",&num);
     list[0]=num;
     res=1;
      for(i=1;i<n;i++)
      {
         scanf("%d",&num);
         if(num>list[res-1]) list[res++]=num;//比当前的数大的话插在后面 
         else 
         if(num<list[res-1])
         {
          w=binary_search(0,res-1,num);//如果小的话在前面找到合适的位置插入
          list[w+1]=num;
         }
      }
     printf("%d\n",res);
  }
  system("pause");
  return 0;
} 

• Re:AC 了 110ms~ (9) I08690127 2009-09-13 16:17:22
• Re:嘿嘿，用时一样 (934) ccsu2008021220 2009-10-04 22:31:48
• Re:AC 了 110ms~ (1216) 070220219 2009-11-11 12:07:17
• 这个nlogn的算法思想在《算法设计与分析习题解答（第2版）》的第76页 (28) 785815369 2010-07-30 13:14:52