longgest.cpp

包括GRAY码

#include <iostream.h>
int main()
{
    int i,j,n,tag,max;
    int *list,*MaxList;
	cout<<"input n:"<<endl;
    cin >> n;
    list=new int[n];
    MaxList=new int[n];
    for (i=1;i<=n;i++)
    {   
		cout<<"input num:";
        cin >> list[i];
        MaxList[i]=0;
    }
    MaxList[n]=1;
    //求最有值，MaxList[i]表示从第i个元素开始的最长递增子序列的长度。 
    for (i=n-1;i>=1;i--)
    {
        for (j=n;j>i;j--)
        {
            if ((list[i]<list[j])&&(MaxList[i]<MaxList[j]+1)) MaxList[i]=MaxList[j]+1;
            if ((list[i]==list[j])&&(MaxList[i]<MaxList[j])) MaxList[i]=MaxList[j];
            if ((list[i]>list[j])&&(MaxList[i]==0)) MaxList[i]=1;
        }
    }
    max=MaxList[1]; 
    tag=1;
    //构造最优解。 
    for (i=2;i<=n;i++)
    {
        if (max<MaxList[i])
        {
            max=MaxList[i];
             tag=i;
        }
    }
    cout << "The List is " << max <<endl; 
    i=tag;
    while (i<=n)
    {
        j=i;
        cout << list[i++]<<" ";
        while (MaxList[j]!=MaxList[i]+1&&i++<=n);
    }
    cin >>i;
    return 0;
}