test4.cpp

算法分析与设计的最长子序列问题

#include<stdio.h>

void main()
{
	int i,k,l=0;
	int h,j,line;
	int b[50];
	int sequence[10][50];
	do{
		scanf("%d",&sequence[l][0]);
		for(i=1;i<=sequence[l][0];i++)
		{
			scanf("%d",&sequence[l][i]);
		}
		l++;
	}while(sequence[l][0]!=0);

	for(line=0;line<l;line++)
	{
		b[1]=sequence[line][1];
		for(i=2,k=1;i<sequence[line][0];i++)
		{
			if(sequence[line][i]>b[k])
				b[++k]=sequence[line][i];
			else
			{
				if(sequence[line][i]<b[j])
					b[1]=sequence[line][i];
				for(h=1,j=k;h!=j-1;)
				{
					if(b[k=(h+j)/2]<sequence[line][i])
						h=k;
					else
						j=k;
				}
				b[j]=sequence[line][i];
			}
		}
		printf("%d\n",k);

	}
}