pku1631.cpp

来自「这是ACM 方面的资料 是PKU的 北京大学的出来的」· C++ 代码 · 共 54 行

#include <stdio.h>
#define SZ 40001
int a[SZ], b[SZ];
int Max;

void search(int x)
{
	int l, h, m;
	if (x < b[0])
	{
		b[0] = x;
		return;
	}
	if (x > b[Max - 1])
	{
		b[Max++] = x;
		return;
	}
	l = 0, h = Max - 1;
	while (h - l > 1)
	{
		m = (h + l) / 2;
		if (b[m] > x)
		{
			h = m;
		}
		else
		{
			l = m;
		}
	}
	b[h] = x;
}

int main()
{
	int T, N, i, j, pos;
	scanf("%d", &T);
	while (T--)
	{
		scanf("%d", &N);
		memset(b, 0, sizeof(b[0]) * (N + 1));
		scanf("%d", &a[0]);
		b[0] = a[0];
		Max = 1;
		for (i = 1; i < N; i++)
		{
			scanf("%d", &a[i]);
			search(a[i]);
		}
		printf("%d\n", Max);
	}
	return 0;
}