最长单调子序列.cpp

给定一个数组

#include<iostream>
#include<ctime>
using namespace std;

#define N 10

void LCSL(int m,int n,int *x,int *y,int **c,int **b);//计算最长公共子序列长度。
void LCS(int i,int j,int *x,int **b);//根据b[i][j]的内容打印a,x数组的最长公共子序列。
void QuickSort(int a[],int p,int r);//快速排序。
int Partition(int a[],int p,int t);//数组划分，将小于等于x的元素移到x左边，大于x的元素移到x右边。
void Swap(int &x,int &y);//交换元素x和y。

//计算最长公共子序列长度
void LCSL(int m,int n,int *x,int *y,int c[][N],int b[][N])
{
	c[0][0]=0;
	int i,j;
	for(i=1;i<=m;i++)
		c[i][0]=0;
	for(i=1;i<=n;i++)
		c[0][i]=0;
	for(i=1;i<=m;i++)
		for(j=1;j<=m;j++)
		{
			if(x[i]==y[j])
			{
				c[i][j]=c[i-1][j-1]+1;
				b[i][j]=1;
			}
			else if(c[i-1][j]>=c[i][j-1])
			{
				c[i][j]=c[i-1][j];
				b[i][j]=2;
			}
			else
			{
				c[i][j]=c[i][j-1];
				b[i][j]=3;
			}
		}
		cout<<c[m][m]<<endl;
}
//根据b[i][j]的内容打印a,x数组的最长公共子序列
void LCS(int i,int j,int *x,int b[][N])
{
	
	if(i==0||j==0) return;
	if(b[i][j]==1)
	{
		LCS(i-1,j-1,x,b); 
		for(int y=1;y<i;y++)
			if(x[y]==x[i])
				return;
			
			cout<<x[i]<<" ";
			
	}
	else if(b[i][j]==2)
	{
		LCS(i-1,j,x,b);
	}
	else
		LCS(i,j-1,x,b);
}
void QuickSort(int a[],int p,int r)
{
	if(p<r)
	{
		int q=Partition(a,p,r);
		QuickSort(a,p,q-1);//对左半段排序
		QuickSort(a,q+1,r);//对右半段排序
	}
}

int Partition(int a[],int p,int r)
{
	int i=p,
		j=r+1;
	int x=a[p];
	//将<x的元素交换到左边区域
	//将>x的元素交换到右边区域
	while(true)
	{
		while(a[--j]>x);
		while((i<j)&&a[++i]<x);
		if(i>=j)break;
		Swap(a[i],a[j]);
	}
	a[p]=a[j];
	a[j]=x;
	return j;
}

void Swap(int &x,int &y)
{
	int t;
	t=x;
	x=y;
	y=t;
}

void main(void)
{
	int *a,*x;
	a=new int[N];
	x=new int[N];
    int b[N][N];
	int c[N][N];
	cout<<"请输入十个数："<<endl;
	for(int i=1;i<N;i++)
	{
		cin>>a[i];
		x[i]=a[i];
	}
	QuickSort(x,1,N-1);
	LCSL(N-1,N-1,a,x,c,b);
    LCS(N-1,N-1,a,b);
}