test.cpp

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

#include<stdio.h>

int sublength(int a[100]);
int binary(int i,int k);
void main()
{
	int i,k=0,n,c;
	int sequence1[100],sequence2[100][100];
	do{
		scanf("%d",&n);
		for(i=0;i<n;i++)
			scanf("%d",&sequence1[i]);
		for(i=0;i<n;i++)
			sequence2[k][i]=sequence1[i];
		k++;
	}while(n!=0);
	for(i=0;i<=k;i++)
	{
		c=sublength(sequence2[i]);
		printf("%d\n",c);
	}
}

int sublength(int a[100])
{
	int i,k;
	int b[100];
	b[1]=a[0];
	for(i=1,k=1;i<100;i++)
	{
		if(a[i]>=b[k])
			b[++k]=a[i];
		else
			b[binary(i,k)]=a[i];
	}
	return k;
}

int binary(int i,int k)
{
	int h,j;
	if(a[i]<b[j])
		return 1;
	for(h=1,j=k;h!=j-1;)
	{
		if(b[k=(h+j)/2]<a[i])
			h=k;
		else
			j=k;
	}
	return j;
}