LIS：一个序列，求它的最长上升子序列的最大长度。
***关于LIS，一般有三种做法，先写下两种吧，一种就是O（n2）的DP算法；一种就是O（nlogn）的二分+贪心算法；还有一种也是O（nlogn）的树状数组的办法，先写一写前两种，以后再补吧。****
解法一：经典做法DP：
思路：
状态设计：dp[i]代表以a[i]结尾的LIS的长度
状态转移：dp[i]=max(dp[i], dp[j]+1) (1<=j< i, a[j]< a[i])
边界处理：dp[i]=1 (1<=i<=n)
时间复杂度：O(N^2)
代码模板：
for(int i=1;i<=n;++i){ dp[i]=1; for(int j=1;j<=i-1;++j){ if(a[j]<a[i]) dp[i]=max(dp[i],dp[j]+1); } ans=max(ans,dp[i]); }
例题：最长上升子序列
Description 一个数的序列bi，当b1< b2 < ... < bS的时候，我们称这个序列是上升的。对于给定的一个序列(a1,a2,...,aN)，我们可以得到一些上升的子序列(ai1, ai2, ..., aiK)，这里1<=i1 < i2 < ... < iK<=N。比如，对于序列(1,7,3,5,9,4,8)，有它的一些上升子序列，如(1,7),(3,4,8)等等。这些子序列中最长的长度是4，比如子序列(1,3,5,8)。 你的任务，就是对于给定的序列，求出最长上升子序列的长度。 Input 输入的第一行是序列的长度N(1<=N<=1000)。第二行给出序列中的N个整数，这些整数的取值范围都在0到10000。 Output 最长上升子序列的长度。 Sample Input 6 1 6 2 5 4 7 Sample Output 4
#include<bits/stdc++.h> using namespace std; int a[105],f[105],i,j,maxx,n; int main() { cin>>n; for(i=1; i<=n; i++) { cin>>a[i]; f[i]=1; } for(i=2; i<=n; i++) for(j=1; j<i; j++) if(a[j]<a[i]) { f[i]=max(f[j]+1,f[i]); } maxx=1; for(i=1; i<=n; i++) if(f[i]>f[maxx])maxx=i; cout<<f[maxx]<<endl; }
解法二：贪心加二分
思路：新建一个 low 数组，low [ i ]表示长度为i的LIS结尾元素的最小值。对于一个上升子序列，显然其结尾元素越小，越有利于在后面接其他的元素，也就越可能变得更长。因此，我们只需要维护 low 数组。
那么，怎么维护 low 数组呢？
对于每一个a [ i ]，如果a [ i ]能接到 LIS 后面，就接上去；否则，就用 a [ i ] 取更新 low 数组。具体方法是，在low数组中找到第一个大于等于a [ i ]的元素low [ j ]，用a [ i ]去更新 low [ j ]。如果从头到尾扫一遍 low 数组的话，时间复杂度仍是O(n^2)。我们注意到 low 数组内部一定是单调不降的，所有我们可以二分 low 数组，找出第一个大于等于a[ i ]的元素。二分一次 low 数组的时间复杂度的O(lgn)，所以总的时间复杂度是O(nlogn)。
有以下序列A[ ] = 3 1 2 6 4 5 10 7，求LIS长度：
因为在B中插入的数据是有序的，不需要移动，只需要替换，所以可以用二分查找插入的位置
代码模板：
int binary_search(int r,int x) { int L=1,mid; while(L<=R){ mid=(L+R)/2;//mid=(L+R)>>1; if(a[mid]<=x) L=mid+1; else R=mid-1; } return L; }
主函数： for(int i=1;i<=n;i++){ cin>>a[i];Low[i]=inf;} Low[1]=a[1];ans=1; for(int i=2;i<=n;i++) { if(a[i]>Low[ans]) Low[++ans]=a[i]; else Low[binary_search(ans,a[i])]=a[i]; } cout<<ans<<endl;
这其中用到了二分查找第一个大于等于的，其实C++里面的有一个函数可用代替二分，那就是 —— lower_bound( )函数。
lower_bound( )函数：返回值是指向大于等于key的值的位置
upper_bound()函数：返回值是大于key的值的位置
对象：有序数组或容器
例如：a[]={1,2,3,4,5}
cout<<lower_bound(a,a+5,3)-a;输出2
cout<<upper_bound(a,a+5,3)-a;输出3
利用lower_bound()函数的做法
fill(Low,Low+n,inf); int ans=-1; for(int i=1;i<=n;i++){ int j=lower_bound(Low+1,Low+1+n,a[i])-Low; d[i]=j; ans=max(ans,d[i]); Low[j]=a[i]; } cout<<ans<<endl;
这里主要注意一下lower_bound函数的应用，注意减去的Low是地址:地址 - 地址 = 下标
解法三：树状数组
https://blog.csdn.net/lxt_Lucia/article/details/81206439?depth_1-utm_source=distribute.pc_relevant.none-task-blog-BlogCommendFromBaidu-1&utm_source=distribute.pc_relevant.none-task-blog-BlogCommendFromBaidu-1
最长公共子序列，英文缩写为LCS（Longest Common Subsequence）。其定义是，一个序列 S ，如果分别是两个或多个已知序列的子序列，且是所有符合此条件序列中最长的，则 S 称为已知序列的最长公共子序列。
动态规划：
LCS(x,y) =
(1) LCS(x - 1,y - 1) + 1 如果Ax ＝ By
(2) max(LCS(x – 1, y) , LCS(x, y – 1)) 如果Ax ≠ By
(3) 0 如果x = 0或者y = 0
例题：
Description 一个给定序列的子序列是在该序列中删去若干元素后得到的序列。确切地说，若给定序列X= < x1, x2,…, xm>，则另一序列Z= < z1, z2,…, zk>是X的子序列是指存在一个严格递增的下标序列 < i1, i2,…, ik>，使得对于所有j=1,2,…,k有 Xij=Zj 例如，序列Z=是序列X=的子序列，相应的递增下标序列为<2,3,5,7>。给定两个序列X和Y，当另一序列Z既是X的子序列又是Y的子序列时，称Z是序列X和Y的公共子序列。例如，若X= < A, B, C, B, D, A, B>和Y= < B, D, C, A, B, A>，则序列是X和Y的一个公共子序列，序列也是X和Y的一个公共子序列。而且，后者是X和Y的一个最长公共子序列，因为X和Y没有长度大于4的公共子序列。 给定两个序列X= < x1, x2, …, xm>和Y= < y1, y2, … , yn>，要求找出X和Y的一个最长公共子序列。 Input 共有两行。每行为一个由大写字母构成的长度不超过200的字符串，表示序列X和Y。 Output 输出仅为一个非负整数。表示所求得的最长公共子序列的长度。若不存在公共子序列．则输出0。 Sample Input ABCBDAB BDCABA Sample Output 4 Hint 最长公共子串（Longest Common Substirng）和最长公共子序列（Longest Common Subsequence，LCS）的区别为：子串是串的一个连续的部分，子序列则是从不改变序列的顺序，而从序列中去掉任意的元素而获得新的序列；也就是说，子串中字符的位置必须是连续的，子序列则可以不必连续。字符串长度小于等于1000。
#include <bits/stdc++.h> using namespace std; const int N=5005; int f[N][N]; int maxx=0; int sum=0; int main() { string s,t; cin>>s; cin>>t; int lens=s.length(),lent=t.length(); for(int i=1;i<=lens;i++) { for(int j=1;j<=lent;j++) { f[i][j]=max(f[i-1][j],f[i][j-1]); if(s[i-1]==t[j-1]) f[i][j]=max(f[i][j],f[i-1][j-1]+1); } } cout<<f[lens][lent]<<endl; return 0; }
给出有 n 个元素的数组 a[] , m 个元素的数组 b[] ,求出它们的最长上升公共子序列的长度.
Description 给定两个整数序列，写一个程序求它们的最长上升公共子序列。 当以下条件满足的时候，我们将长度N的序列S1,S2,...,SN称为长度为M的序列A1,A2,...,AM的上升子序列： 存在1<= i1 < i2 <...< iN <= M，使得对所有 1 <= j <= N，均有Sj=Aij，且对于所有的1 <= j < N，均有Sj < Sj+1。 Input 每个序列用两行表示，第一行是长度M( 1<=M<=500)，第二行是该序列的M个整数Ai( −2^31<=Ai<2^31) Output 在第一行，输出两个序列的最长上升公共子序列的长度L。在第二行，输出该子序列。如果有不止一个符合条件的子序列，则输出位置最靠前的一个。 Sample Input 5 1 4 2 5 -12 4 -12 1 2 4 Sample Output 2 1 4
确定状态
可以定义 dp[i][j] 表示以 a 数组的前 i 个整数与 b 数组的前 j 个整数且以 b[j] 为结尾构成的公共子序列的长度。
对于解决DP问题,第一步定义状态是很重要的!
需要注意，以 b[j] 结尾构成的公共子序列的长度不一定是最长公共子序列的长度！
状态转移方程:
① a[i] != b[j], dp[i][j] = dp[i-1][j]② a[i] == b[j], dp[i][j] = max(dp[i-1][k]+1) (1 <= k <= j-1 && b[j] > b[k])
O(N * M)算法
分析：到这里好像没有更好的方法来优化查找了，那让我们再仔细的分析一下问题。
当a[i] != b[j], dp[i][j] = dp[i-1][j],这对问题并没有什么影响。
当a[i] == b[j]，的时候 dp[i][j] = max(dp[i-1][k]+1) (1 <= k <= j-1 && b[j] > b[k])，我们发现一个特点，其实 a[i] ( b[j] )与 b[k] 的关系早就在之前就可以确定了！( i 是最外层循环， j` 是内层循环，当 j` 遍历到 k 时，就足以判断 b[j] ? b[j`] 的大小关系了)，因此我们只需要在内层循环与外层循环直接维护一个 max_dp 的值，等到 a[i] == b[j] 的时候，直接令 dp[i][j] = max_dp + 1即可，时间复杂度降到了 O(N * M)。
| 5 | -12 | 1 | 2 | 4 | 5 | |
| 1 | 0 | 0 | 1 | 0 | 0 | 0 |
| 4 | 0 | 0 | 1 | 0 | 2 | 0 |
| 2 | 0 | 0 | 1 | 2 | 2 | 0 |
| 5 | 1 | 0 | 1 | 2 | 2 | 3 |
| -12 | 1 | 1 | 1 | 2 | 2 |
3 |
for (int i = 1 ; i <= n ; ++i) { int max_dp = 0; for (int j = 1 ; j <= m ; ++j) { dp[i][j] = dp[i-1][j]; if (a[i] > b[j]&& max_dp < dp[i-1][j]) max_dp = dp[i][j]; else if (a[i] == b[j]) { dp[i][j] = max_dp + 1; } ans = max(ans, dp[i][j]); } }
将空间复杂度优化
int main() { scanf("%d",&t); while(t--) { scanf("%d%d",&n1,&n2); for(i=1;i<=n1;i++) scanf("%d",&a[i]); for(i=1;i<=n2;i++) scanf("%d",&b[i]); memset(f,0,sizeof(f)); for(i=1;i<=n1;i++) { max=0; for(j=1;j<=n2;j++) { if (a[i]>b[j]&&max<f[j]) max=f[j]; if (a[i]==b[j]) f[j]=max+1; } } max=0; for(i=1;i<=n2;i++) if (max<f[i]) max=f[i]; printf("%d\n",max); } }
例题：
/*************************************************** LCIS:最长公共上升子序列 求序列 A 长度为 N 和序列 B 长度为 M 的 LCS 序列下标从 1 开始 返回 LCS 长度 *****************************************************/ int dp[maxn]; int LCS(int n, int m) { memset(dp, 0, sizeof(dp)); for(int i = 1; i <= n; i++) { int tmp = 0; // 存 i 确定, 且 a[i] > b[j] 时最大的 dp[j] for(int j = 1; j <= m; j++) { if(a[i] > b[j] && dp[j] > tmp) tmp = dp[j]; else if(a[i] == b[j]) dp[j] = tmp+1; } } int ans = 0; for(int i = 1; i <= m; i++) ans = max(ans, dp[i]); return ans; }
原文：https://www.cnblogs.com/sunny99/p/12628382.html
