a.cpp

求最长的公共子序列

#include<stdio.h>
#include<stdlib.h>
int compare(const void *p1,const void *p2)
{
	return *((int *)p1) - *((int *)p2);
}

int LCS(int *a,int *b,int n,int m,int c[1002][1002])
{
	int i;
	int j;
	for(i = 1;i<=m;i++)
	{
		for(j = 1;j<=n;j++)
		{
			if(a[i-1] == b[j-1])
			{
				c[i][j] = c[i-1][j-1] + 1;			
			}
			else
			{					
				c[i][j] = c[i][j-1]>c[i-1][j]?c[i][j-1]:c[i-1][j];
			}
		//	printf("%d %d %d:\n",i,j,c[i][j]);
		}
	}
	return c[m][n];
}

int main()
{
	int a[1001];
	int b[1001];
	int c[1002][1002];
	int d[1001];
	int n;
	int i;
	scanf("%d",&n);
	for(i = 0;i<n;i++)
	{
		scanf("%d",&a[i]);
		b[i] = a[i];
	}
	for(i = 0;i<=n;i++)
	{
		c[i][0] = 0;
		c[0][i] = 0;
	}
	qsort(a,n,sizeof(a[0]),compare);
	int k = 1;
	d[0] = a[0];
	for(i = 1;i<n;i++)
	{
		if(a[i]>d[k-1])
		{
			d[k++] = a[i];
		}
	}
	LCS(d,b,n,k,c);
	printf("%d\n",c[k][n]);
	return 0;
}