共计 1033 个字符，预计需要花费 3 分钟才能阅读完成。
该题目有两种解法，都是动态规划中特别经典的解法，一种是最长不下降子序列，一种是最长公共子序列；
第一种方法对于该题目其实有点取巧的感觉；首先，注意一点，对于最长不下降子序列来说，其序列的元素一定是非递减的，所以我们的当务之急是如何将值转换为递增序列，从而使得算法能够继续进行；对于这个问题，我们可以使用 hashtable 进行处理，也就是利用 hashtable 重新使得值递增；
这里需要注意一下，子序列递增研究的是不连续的子序列，连续的子序列其实可以用前面的 KMP 算法来及进行解决；对于该问题，首当其中的还是状态转移方程。由于该问题还是从 0 开始研究，所以仍然设置一个一维数组 dp 来储存中间的状态；
大致思路是限定一个子串序列，然后选择一个，从第一个开始进行轮询，这里有点像插入排序的感觉；其状态转移方程为 dp[i]=max(1,dp[j]+1); 该方程可以理解将第 i 个元素排在 j 后面，从而继承 j 之前的子串序列的长度，1 为单个元素的序列长度；代码如下：
#include<iostream>
#include<stdio.h>
#include<stdlib.h>
#include<algorithm>
using namespace std;
const int maxc=210;
const int maxn=10010;
int Hashtable[maxc];
int a[maxn],dp[maxn];
int main(){
int n,m,x;
scanf(“%d%d”,&n,&m);
memset(Hashtable,-1,sizeof(Hashtable));
for(int i=0;i<m;i++){
scanf(“%d”,&x);
Hashtablet[x]=i;
}
int L,num=0;
scanf(“%d”,&L);
for(int i=0;i<L;i++){
scanf(“%d”,&x);
if(Hashtable[x]>=0){
a[num++]=Hashtable[x];
// 进行 hashtable 的相应转换
}
}
int ans=-1;
for(int i=0;i<num;i++){
dp[i]=1;
for(int j=0;j<i;j++){
if(a[j]<=a[i]&&dp[i]<dp[j]+1){
dp[i]=dp[j]+1;
}
}
ans=max(ans,dp[i]);
}
printf(“%d\n”,ans);
return 0;
}
第二种不太好理解，所以这里先不再赘述，主要是不能理解为什么公共部分可以重复输出；
