最长上升子序列（LIS) 、最长公共子序列（LCS)
一、最长上升子序列 （LIS)（一般好像没有遇到过输出最长上升子序列元素的情况，所以就没整理）
为DP问题，所以我们可以用DP来解决。
它有两种算法：
1、 时间复杂度为O（n^2）——dp 解决
递推关系：
dp[i]={1,d[j]+1|j<i且aj<ai}
dp[]：代表 以 ai 为末尾的最长上升子序列的长度
而以ai结尾的上升子序列又包含两种情况：
（1）只包含ai的子序列
（2）在满足 j<i 并且 aj<ai 的以aj 为结尾的上升子列末尾，追加上ai 后得到的子序列。
我们依次遍历整个序列，每一次求出从第一个数到当前这个数的最长上升子序列，直至遍历到最后一个数字为止，然后
再取dp数组里最大的那个即为整个序列的最长上升子序列。我们用dp[i]来存放序列1-i的最长上升子序列的长度，那么dp[i]=max(dp[j])+1,(j∈[1, i-1]); 显然dp[1]=1,我们从i=2开始遍历后面的元素即可
代码如下：
#include <iostream>
#include <algorithm>
#include <stdio.h>
#include <cstring>
using namespace std;
const int N=1e6;
int n,a[N],dp[N];
void f() //求最长上升子序列
{
int ans=0;
for(int i=1;i<=n;i++)
{
dp[i]=1;
for(int j=1;j<=n;j++)
if(a[j]<a[i])
dp[i]=max(dp[i],dp[j]+1);
ans=max(dp[i],ans);
}
cout<<ans<<endl;
}
int main()
{
memset(a,0,sizeof(a));
memset(dp,0,sizeof(dp));
cin>>n;
for(int i=1;i<=n;i++)
cin>>a[i];
f();
return 0;
}2、时间复杂度为O（nlogn）——二分法解决
Code：
（1）、用到了二分法的两个函数，这篇博客有详细介绍
#include <cstdio>
#include <cstring>
#include <algorithm>
#include <iostream>
#define MAXN 40005
using namespace std;
int arr[MAXN],ans[MAXN],len;
int main()
{
int n;
int T;
cin>>T;
while(T--)
{
cin>>n;
for(int i=1; i<=n; ++i)
scanf("%d",&arr[i]);
ans[1] = arr[1];
len=1;
for(int i=2; i<=n; ++i)
{
if(arr[i]>ans[len])
ans[++len]=arr[i];
else
{
int pos=lower_bound(ans,ans+len,arr[i])-ans;
ans[pos] = arr[i];
}
}
cout<<len<<endl;
}
return 0;
}（2）、普通的二分，控制左右端点
Code:
#include<iostream>
#include<cstdio>
#include<cstring>
#include<algorithm>
const int MAX=50000;
using namespace std;
int arr[MAX+50],ans[MAX+50],len;
int binary_search(int i)//手写二分法
{
int left,right,mid;
left=0,right=len;
while(left<right)
{
mid = left+(right-left)/2;
if(ans[mid]>=arr[i]) right=mid;
else left=mid+1;
}
return left;
}
int main()
{
int n;
cin>>n;
for(int i=1; i<=n; i++)
cin>>arr[i];
ans[0] = arr[1];
len=0;
for(int i=2; i<=n; i++)
{
if(arr[i]>ans[len])
ans[++len]=arr[i];
else
{
int pos=binary_search(i)；
ans[pos] = min(ans[pos],arr[i]);
}
}
cout<<len+1<<endl;//数组大小就是最长上升子序列的个数
}二、最长公共子序列（LCS) （ 有的题目需要进行回溯，输出哪些是公共的元素）
z0,z1, z2,......zk-1 为最长上升子序列的长度的话
（1）、若 Sn-1=Tm-1=zk-1 的话，
则 z0...zk-2 为 S0,S1...Sn-2 和 T0,T1...Tn-2 的最长公共子序列
（2）、若 Sn-1 ！= Tm-1的话，
分了两种情况
（1）、Sn-1 ！=zk-1 && Tm-1 =zk-1，z0...zk-1 是 S0,S1...Sn-2 和 T0,T1...Tn-1 的最长公共子序列
（2）、Tm-1 ！=zk-1 && Sn-1 =zk-1，z0...zk-1 是 S0,S1...Sn-1 和 T0,T1...Tn-2 的最长公共子序列
比较两个数组 s[i] t[i] 共同元素的最长长度
引进一个二维数组dp[][]，用 dp[i][j] 记录s[i]与t[j] 的LCS 的长度.
我们是自底向上进行递推计算，那么在计算dp[i,j]之前，dp[i-1][j-1]，dp[i-1][j]与dp[i][j-1] 均已计算出来。
此时我们根据s[i] = t[j]还是s[i] != t[j]，就可以计算出dp[i][j]。
问题的递归式写成：
介绍一下递归式：
如果当前两个字符串为 0的话，长度就是 0;
如果当前两个字符相等的话，可以看成以当前字符结尾的子序列，由上一个状态的长度加 1得到的 ；
如果不相等的话，就去找一个最大值
首先做初始化。将 dp[0][i] 和从 dp[i][0] 初始化为0，然后一行一行的填表
Code：
#include <iostream>
#include <algorithm>
#include <cstring>
#include <cstdio>
using namespace std;
const int N=1e6;
int dp[500][500];
char s[1000],t[1000];
int n,m;
void f()
{
for(int i=0;i<n;i++)
for(int j=0;j<m;j++)
if(s[i]==t[j])
dp[i+1][j+1]=dp[i][j]+1;
else
dp[i+1][j+1]=max(dp[i][j+1],dp[i+1][j]);
cout<<dp[n][m]<<endl;
}
int main()
{
scanf("%s%s",s,t);
n=strlen(s);
m=strlen(t);
f();
return 0;
}回溯输出最长公共子序列过程：
Code ：
void BUILD_LCS(int len,int len1)
{
if(len==0||len1==0)
return ;
if(s[len-1]==c[len1-1]){
BUILD_LCS(len-1,len1-1);
cout<<c[len1-1];
}
else{
if(dp[len-1][len1]>dp[len][len1-1])
BUILD_LCS(len-1,len1);
else
BUILD_LCS(len,len1-1);
}
}