lis.txt

实现求解整数的递增子序列。给出一串整数

#include<iostream.h>
#include <string.h>
void quickSort(int a[],int left,int right);
int LCS(int A[],int n,int m);
int H[1000][1000];
void main()
{   
	int syscle,s;
	cin>>syscle;
	for (s=1;s<=syscle;s++)
	{
		int x,y,i,j,length,k;
	int *C,*A;
	cin>>x;
	A=new int[1000];
	for(i=1;i<=x;i++)
		cin>>A[i];
	C=new int[100];
	y=x;
	i=x;  
	j=y;  
	length=LCS(A,x,y);
	k=length;
    while (i>0 && j>0)
	{
         if (H[i][j]==0)
		 {   
			 C[--k]=A[i];	 
             i=i-1;  
		     j=j-1;
		 }
         else if (H[i][j]==1) 
		     i=i-1 ;
		 else 
		     j=j-1 ; 
	}
	cout<<length<<endl;
    for(k=0;k<length;k++)
             cout<<C[k]<<" ";
	cout<<endl;
	}
}
int LCS(int A[],int n,int m)
{
	int L[500][500];
	int i,j;
	int *B;
	B=new int[1000];
	for(i=1;i<=n;i++)
	{
		B[i]=A[i];
	}	
	quickSort(B,1,n); //快速排序

    for(i=0;i<n;i++)
	{
		L[i][0]=0;
	}
    for(j=0;j<m;j++)
	{
	    L[0][j]=0;
	}

	for(i=1;i<=n;i++)
		for(j=1;j<=m;j++)
			if (A[i]==B[j])
			{
				L[i][j]=L[i-1][j-1]+1;
				H[i][j]=0;
			}
			else if (L[i-1][j]>=L[i][j-1])
			{
				L[i][j]=L[i-1][j];
				H[i][j]=1;
			}
			else
			{
				L[i][j]=L[i][j-1];
				H[i][j]=2;	
			}
	return L[n][m];
}

void quickSort(int a[],int left,int right)
{
   int i,j,temp;
   i=left;
   j=right;
   temp=a[left];
   if(left>right)
      return;
   while(i!=j)   
   {
      while(a[j]>=temp && j>i)
         j--;
      if(j>i)
         a[i++]=a[j];
       while(a[i]<=temp && j>i)
          i++;
       if(j>i)
          a[j--]=a[i];
         
   }
   a[i]=temp;
   quickSort(a,left,i-1);       
   quickSort(a,i+1,right);      
}