职务地址：HDU 1950

这题是求最长上升序列，可是普通的最长上升序列求法时间复杂度是O(n*n)。显然会超时。于是便学了一种O(n*logn)的方法。也非常好理解。

感觉还用到了一点贪心的思想。

详细的见这篇博客吧，写的非常通俗易懂。传送门

代码例如以下：

#include <iostream>

#include <cstdio>

#include <string>

#include <cstring>

#include <stdlib.h>

#include <math.h>

#include <ctype.h>

#include <queue>

#include <map>

#include <set>

#include <algorithm>

using namespace std;

#define LL long long

int a[50000], b[50000], len;

int bin_seach(int x)

{

    int low=1, high=len, mid, ans;

    while(low<=high)

    {

        mid=low+high>>1;

        if(b[mid]>=x) {high=mid-1;ans=mid;}

        else low=mid+1;

    }

    return ans;

}

int main()

{

    int t, n, i, pos;

    scanf("%d",&t);

    while(t--)

    {

        scanf("%d",&n);

        for(i=0;i<n;i++)

        {

            scanf("%d",&a[i]);

        }

        len=0;

        b[++len]=a[0];

        for(i=1;i<n;i++)

        {

            if(a[i]>b[len])

            {

                b[++len]=a[i];

            }

            else

            {

                pos=bin_seach(a[i]);

                b[pos]=a[i];

            }

        }

        printf("%d\n",len);

    }

    return 0;

}