以前写过一遍。这个算法很不错，时间是O(nlogn)，空间是O(n)，使用了一个栈。

CQF大牛的算法：

1、建立一个栈stack，清空。{stack[i]表示当前状态下，所有长度为i的子序中最后一个数的最小值}。//这个太漂亮了：cqf是大牛大牛大大牛呀：）

2、按先后顺序循环序列的每一个数，用操作3修改当前状态

3、如果这个数不小栈顶或栈为空就++stack的长度，否则就用二分法找出一个最小的i使得stack[i]>这个数.将stack[i]更新为这个数。{可以用二分法是因为stack是有序的}

4、输出stack的长度。{最长不下子序长度}

#include <cstdio>
#include <string>

int a[40000], c;

int main()
{
 int m, n, i, k;
 //freopen("in.txt", "r", stdin);
 scanf("%d", &m);
 for(i = 0; i < m; i ++)
 {
  memset(a, 0, sizeof(a));
  scanf("%d", &n);
  c = 0;
  for(k = 0; k < n; k ++)
  {
   int t;
   scanf("%d", &t);
   if(c == 0 || t > a[c - 1])
    a[c ++] = t;
   else
   {
    int l = 0, h = c - 1, mid = (l + h) / 2;
    while(l < h)
    {
     if(a[mid] < t) l = mid + 1;
     else if(a[mid] > t) h = mid;
     mid = (l + h) / 2;
    }
    a[mid] = t;
   }
   //pa();
  }
  printf("%d\n", c);
 }
 return 0;
}

评论