/*
课本3-1-1。

程序功能：求解最长公共递增子序列

经过vc8.0编译通过
*
*/
#include <iostream>
#include <string.h>
using namespace std;
#define N  11
//———————————————————
//最长公共子序列求解
int lcslength(int * x,int m,int * y,int n,int (*b)[N])
{

int c[N][N];
int i;
for(i=0;i<=n;i++) {c[0][i]=0;c[i][0]=0;}
for(i=1;i<=m;i++)
{
for(int j=1;j<=n;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;
}

}

}
for(i=1;i<=m;i++)
{
for(int j=1;j<=n;j++)
cout<<c[i][j]<<”  “;
cout<<endl;
}
return c[m][n];
}

//———————————————————-
//输出最长公共子序列
int lcs(int i,int j,int *x, int (*b)[N] ,int *resualt)
{
int static count =0;
if(i==0||j==0) return count;
if(b[i][j]==1)
{
lcs(i-1,j-1,x,b,resualt);
cout<<x[i]<<endl;
resualt[count++]=x[i];
}
else if(b[i][j]==2)
lcs(i-1,j,x,b,resualt);
else
lcs(i,j-1,x,b,resualt);
}
//—————————————————————-
//求解最长公共递增子序列
void  lcsuplength(int * x ,int count)
{
int (*h)[2];
h=new int [count][2];
//h[i][0]存放x[i]前面的最长递增子序列的长度
//h[i][1]存放x[i]所在递增序列中他前面的那个元素得下标

//初始化 每个元素的序列长度为1
h[0][1]=0;//0号元素前面的数为他自己
for(int i=0;i<count ;i++)
{
h[i][0]=1;
}

for(int j=1;j<count;j++)
for(int i=j-1;i>=0;i–)
if(x[i]<x[j]&&h[i][0]>=h[j][0])//与他前面的数比较   如果前面的数比他小 且 前面的数的序列长度大于等于他的
{

h[j][0]=h[i][0]+1;
h[j][1]=i;
}

//找出最大序列
int j=0;
int max=h[0][0];
for(int i=1;i<count ;i++)
if(h[i][0]>max)
{
h[i][0]=max;
j=i;
}
cout<<“将输出翻过来就是结果”<<endl;
//循环输出结果
while(1)
{
if(h[j][1]==j)
{
cout<<x[j]<<”   “;
break;
}
else
{
cout<<x[j]<<”   “;
j=h[j][1];
}
}
delete [count]h;

}

//——————————————————————-
//入口函数
int main()
{
int x[]={0,4,9,8,5,6,10,11,12,14,19,1};
int y[]={0,4,9,8,5,6,10,11,12,14,19,2};
int b[11][11];
cout<<“______c数组输出__________________”<<endl;
int count=lcslength(x,10,y,10,b);
cout<<“______b数组输出__________________”<<endl;
for(int i=1;i<11;i++)
{
for(int j=1;j<11;j++)
cout<<b[i][j]<<”  “;
cout<<endl;
}
cout<<“—————最长公共子序列———–“<<endl;
int* ope=new int [count];
lcs(10,10,x, b,ope);
cout<<“公共元素数量:”<<count<<endl;
cout<<endl;
cout<<endl;

cout<<“—————最长公共递增子序列———–“<<endl;

lcsuplength(ope,count);

delete []ope;

return 0;
}