描述
给定两个整数序列，写一个程序求它们的最长上升公共子序列。
当以下条件满足的时候，我们将长度为N的序列S1 , S2 , . . . , SN 称为长度为M的序列A1 , A2 , . . . , AM 的上升子序列：
存在1 <= i1 < i2 < . . . < iN <= M ，使得对所有 1 <= j <=N，均有Sj = Aij，且对于所有的1 <= j < N，均有Sj < Sj+1。
输入
每个序列用两行表示，第一行是长度M(1 <= M <= 500)，第二行是该序列的M个整数Ai (-231 <= Ai < 231 )
输出
在第一行，输出两个序列的最长上升公共子序列的长度L。在第二行，输出该子序列。如果有不止一个符合条件的子序列，则输出任何一个即可。
样例输入
51 4 2 5 -124-12 1 2 4
样例输出
21 4
题目分析
本题是典型的动态规划问题中的公共子序列问题的升级版本，在要求子序列的基础上又增加了递增的要求，这一要求使得原本的核心公式不再适用。
在本题的解决方案中，还是采用了一个二维数组作为动态规划表格，并留出每一行的第一列记录公共子序列长度，而每一行记录不同情况下的公共子序列。
算法过程为以s2为大循环，用s1的每一项与s2的第j项比较，s2[j]>s1[i]&&s[0]<t[i][0]情况下，即符合局部上升且之前存储过公共子序列时，将之前存储的公共子序列调出，s1[i]==s2[j]情况下，即发现公共项时，将其放入调出子序列的后面，并记录现有长度，待i循环完毕，将s置零。
两重循环完毕后，表格变为每行第一个为值为公共上升子序列长度，其后跟随该情况下的公共上升子序列。
数据结构
只用了一个二维数组，三个一位数组。
代码及算法说明
#include<stdio.h>
#include<string.h>
int s1[501],s2[501],t[501][501]={0},s[501];
int main()
{
int m,n,ans=0,i,j;
scanf("%d",&m);
for(i=1;i<=m;i++)scanf("%d",&s1[i]);
scanf("%d",&n);
for(i=1;i<=n;i++)scanf("%d",&s2[i]);
s1[0]=s2[0]=-99999; //尽可能小，确保后面判断。
for(j=1;j<=n;j++)
{
memset(s,0,sizeof(s)); //将s置零。
for(i=1;i<=m;i++)
{
if(s2[j]>s1[i]&&s[0]<t[i][0])
memcpy(s,t[i],sizeof(t[i])); //将t[i]复制给s，即调出之前存储的公共上升子序列。
if(s1[i]==s2[j])
{
memcpy(t[i],s,sizeof(s)); //将s复制给t[i]，即存储当前情况下子序列。
t[i][++t[i][0]]=s1[i]; //接上子序列，并计入长度+1。
}
}
}
for(i=1;i<=m;i++)
if(ans<t[i][0]) ans=t[i][0]; //寻找最大长度。
printf("%d\n",ans);
for(i=1;i<=m;i++)
if(t[i][0]==ans)
{
for(j=1;j<=t[i][0];j++) printf("%d ",t[i][j]);
break;
}
return 0;
}
算法分析
1.该算法借鉴了网上的一些答案，之前没有看到要求递增，考虑之后发现大有不同，有些时候很容易被相似题目名称误导，耽误时间和精力。
2.使用了string.h中的memcpy()和memset()函数，使代码更加简洁。
3.本题还是采用了动态规划惯用的制作表格，但是其采用每一行的0位记录长度，并且核心制表代码精简巧妙，值得学习。
4.本代码中有许多小细节比较巧妙，利用简化代码和减少复杂度。