//二分图不交叉最大匹配问题其实就是最长递增序列问题
#include<iostream>
using namespace std;

const int SIZE=40010;

int map[SIZE];
int arr[SIZE];
int l;//跟踪记录arr的长度
int Max;

void append(int x);
void change(int x);
int main()
{
	//freopen("input.txt","r",stdin);
	int i;
	int n;
	int cases;
	cin>>cases;
	while(cases--)
	{
		memset(arr,0,sizeof(arr));
		Max=-1; l=0;
		cin>>n;
		for(i=1;i<=n;i++){
			scanf("%d",&map[i]);
			if(map[i]>Max) append(map[i]);
			else change(map[i]);
		}
		cout<<l<<endl;
	}
	return 0;
}

void append(int x)
{
	arr[l]=x;
	Max=arr[l];
	l++;
}

void change(int x)
{
	int low=0,high=l-1;
	int i;
	if(x<arr[0]) high=0;
	else{
		while(high-low>1)
		{
			i=(low+high)/2;
			if(arr[i]<x) low=i;
			else high=i;//if(arr[i]>x) 此题的条件决定了不可能有arr[i]==x的情况发生
		}
	}
	arr[high]=x;
	Max=arr[l-1];
}

• Re:Nlog2(N) (997) jiangfan87 2010-08-11 16:12:14