LIS（最长上升子序列）问题的三种求解方法以及一些例题
转自：https://blog.csdn.net/George__Yu/article/details/75896330
摘要
本篇博客介绍了求LIS的三种方法，分别是O(n^2)的DP，O(nlogn)的二分+贪心法，以及O(nlogn)的树状数组优化的DP，后面给出了5道LIS的例题。
LIS的定义
一个数的序列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).
LIS长度的求解方法
解法1：动态规划
状态设计：F[i]代表以A[i]结尾的LIS的长度
状态转移：F[i]=max{F[j]+1}(1<=j< i,A[j]< A[i])
边界处理：F[i]=1(1<=i<=n)
时间复杂度：O(n^2)
代码：
#include <iostream>
#include <cstdio>
#include <algorithm>
#include <cstdlib>
#include <cstring>
#include <cmath>
using namespace std;
const int maxn = 103,INF=0x7f7f7f7f;
int a[maxn],f[maxn];
int n,ans=-INF;
int main()
{
scanf("%d",&n);
for(int i=1;i<=n;i++)
{
scanf("%d",&a[i]);
f[i]=1;
}
for(int i=1;i<=n;i++)
for(int j=1;j<i;j++)
if(a[j]<a[i]) f[i]=max(f[i],f[j]+1);
for(int i=1;i<=n;i++)
ans=max(ans,f[i]);
printf("%d\n",ans);
return 0;
}解法2：贪心+二分
思路：
新建一个low数组，low[i]表示长度为i的LIS结尾元素的最小值。对于一个上升子序列，显然其结尾元素越小，越有利于在后面接其他的元素，也就越可能变得更长。因此，我们只需要维护low数组，对于每一个a[i]，如果a[i] > low[当前最长的LIS长度]，就把a[i]接到当前最长的LIS后面，即low[++当前最长的LIS长度]=a[i]。
那么，怎么维护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)。
代码
#include <iostream>
#include <cstdio>
#include <algorithm>
#include <cstdlib>
#include <cstring>
#include <cmath>
using namespace std;
const int maxn =300003,INF=0x7f7f7f7f;
int low[maxn],a[maxn];
int n,ans;
int binary_search(int *a,int r,int x)
//二分查找，返回a数组中第一个>=x的位置
{
int l=1,mid;
while(l<=r)
{
mid=(l+r)>>1;
if(a[mid]<=x)
l=mid+1;
else
r=mid-1;
}
return l;
}
int main()
{
scanf("%d",&n);
for(int i=1;i<=n;i++)
{
scanf("%d",&a[i]);
low[i]=INF;//由于low中存的是最小值，所以low初始化为INF
}
low[1]=a[1];
ans=1;//初始时LIS长度为1
for(int i=2;i<=n;i++)
{
if(a[i]>=low[ans])//若a[i]>=low[ans]，直接把a[i]接到后面
low[++ans]=a[i];
else //否则，找到low中第一个>=a[i]的位置low[j]，用a[i]更新low[j]
low[binary_search(low,ans,a[i])]=a[i];
}
printf("%d\n",ans);//输出答案
return 0;
}解法3：树状数组维护
我们再来回顾O(n^2)DP的状态转移方程：F[i]=max{F[j]+1}(1<=j< i,A[j]< A[i])
我们在递推F数组的时候，每次都要把F数组扫一遍求F[j]的最大值，时间开销比较大。我们可以借助数据结构来优化这个过程。用树状数组来维护F数组（据说分块也是可以的，但是分块是O(n*sqrt(n)）的时间复杂度，不如树状数组跑得快），首先把A数组从小到大排序，同时把A[i]在排序之前的序号记录下来。然后从小到大枚举A[i]，每次用编号小于等于A[i]编号的元素的LIS长度+1来更新答案，同时把编号小于等于A[i]编号元素的LIS长度+1。因为A数组已经是有序的，所以可以直接更新。有点绕，具体看代码。
代码：
#include <iostream>
#include <cstdio>
#include <algorithm>
#include <cstdlib>
#include <cstring>
#include <cmath>
using namespace std;
const int maxn =103,INF=0x7f7f7f7f;
struct Node{
int val,num;
}z[maxn];
int T[maxn];
int n;
bool cmp(Node a,Node b)
{
return a.val==b.val?a.num<b.num:a.val<b.val;
}
void modify(int x,int y)//把val[x]替换为val[x]和y中较大的数
{
for(;x<=n;x+=x&(-x)) T[x]=max(T[x],y);
}
int query(int x)//返回val[1]~val[x]中的最大值
{
int res=-INF;
for(;x;x-=x&(-x)) res=max(res,T[x]);
return res;
}
int main()
{
int ans=0;
scanf("%d",&n);
for(int i=1;i<=n;i++)
{
scanf("%d",&z[i].val);
z[i].num=i;//记住val[i]的编号，有点类似于离散化的处理，但没有去重
}
sort(z+1,z+n+1,cmp);//以权值为第一关键字从小到大排序
for(int i=1;i<=n;i++)//按权值从小到大枚举
{
int maxx=query(z[i].num);//查询编号小于等于num[i]的LIS最大长度
modify(z[i].num,++maxx);//把长度+1，再去更新前面的LIS长度
ans=max(ans,maxx);//更新答案
}
printf("%d\n",ans);
return 0;
}例题
Tips：例题1、4可以用来测试n^2的算法，例题2、3、5可以用来测试nlogn的算法
1.洛谷【p1020】导弹拦截
题目描述
某国为了防御敌国的导弹袭击，发展出一种导弹拦截系统。但是这种导弹拦截系统有一个缺陷：虽然它的第一发炮弹能够到达任意的高度，但是以后每一发炮弹都不能高于前一发的高度。某天，雷达捕捉到敌国的导弹来袭。由于该系统还在试用阶段，所以只有一套系统，因此有可能不能拦截所有的导弹。
输入导弹依次飞来的高度（雷达给出的高度数据是不大于30000的正整数），计算这套系统最多能拦截多少导弹，如果要拦截所有导弹最少要配备多少套这种导弹拦截系统。
输入输出格式
输入格式：
一行，若干个正整数最多100个。
输出格式：
2行，每行一个整数，第一个数字表示这套系统最多能拦截多少导弹，第二个数字表示如果要拦截所有导弹最少要配备多少套这种导弹拦截系统。
输入输出样例
输入样例#1：
389 207 155 300 299 170 158 65
输出样例#1：
6
2
题解
第一问是求序列的最长下降子序列，第二问是求序列的最长上升子序列。
第二问的具体证明见http://blog.csdn.net/xiaohuan1991/article/details/6956629
代码：
#include <iostream>//O(n^2)
#include <cstdio>
#include <algorithm>
#include <cstdlib>
#include <cstring>
#include <cmath>
using namespace std;
const int maxn = 103,INF=0x7f7f7f7f;
int a[maxn],f[maxn];
int n,ans,i,j;
int main()
{
for(n=0;~scanf("%d",&a[n+1]);n++) f[n+1]=1;
for(i=1;i<=n;i++)
for(int j=1;j<i;j++)
if(a[j]>a[i]) f[i]=max(f[i],f[j]+1);
for(i=1,ans=-INF;i<=n;i++) ans=max(ans,f[i]);
printf("%d\n",ans);
for(i=1;i<=n;i++) f[i]=1;
for(i=1;i<=n;i++)
for(j=1;j<i;j++)
if(a[j]<a[i]) f[i]=max(f[i],f[j]+1);
for(i=1,ans=-INF;i<=n;i++) ans=max(ans,f[i]);
printf("%d\n",ans);
return 0;
}2.洛谷【p2757】导弹的召唤（数据加强版）
题目描述
同导弹拦截
数据范围
n<=300000
题解
使用O(nlogn)的算法求解
代码：
#include <iostream>//O(nlogn)
#include <cstdio>
#include <algorithm>
#include <cstdlib>
#include <cstring>
#include <cmath>
using namespace std;
const int maxn =300003,INF=0x7f7f7f7f;
int f1[maxn],low1[maxn],f2[maxn],low2[maxn],a[maxn];
int n,ans;
int bs1(int *a,int r,int x)//返回a数组中第一个小于等于x的位置
{
int l=1,mid;
while(l<=r)
{
mid=(l+r)>>1;
if(a[mid]>=x)
l=mid+1;
else
r=mid-1;
}
return l;
}
int bs2(int *a,int r,int x)//返回a数组中第一个大于x的位置
{
int l=1,mid;
while(l<=r)
{
mid=(l+r)>>1;
if(a[mid]<x)
l=mid+1;
else
r=mid-1;
}
return l;
}
int main()
{
for(n=0;~scanf("%d",&a[n+1]);n++)
{
f2[n+1]=f1[n+1]=1;
low1[n+1]=-INF;
low2[n+1]=INF;
}
low1[1]=a[1];//low[i]表示长度为i的最长下降子序列末尾的最大值
ans=1;
for(int i=2;i<=n;i++)
{
if(a[i]<=low1[ans]) low1[++ans]=a[i];//如果a[i]比当前最长下降子序列的末尾小，直接接到后面
else low1[bs1(low1,ans,a[i])]=a[i];//否则，在low1数组中找到第一个小于等于a[i]的位置，用a[i]替换
}
printf("%d\n",ans);
low2[1]=a[1];
ans=1;
for(int i=2;i<=n;i++)
{
if(a[i]>low2[ans]) low2[++ans]=a[i];
else low2[bs2(low2,ans,a[i])]=a[i];
}
printf("%d\n",ans);
return 0;
}3.POJ1631 Bridging signals
题目大意
有p条线路，它们有可能相交。现在让你去掉一些线路，使得剩下的线不相交且线最多（p<40000）。
输入格式：On the first line of the input, there is a single positive integer n, telling the number of test scenarios to follow. Each test scenario begins with a line containing a single positive integer p < 40000, the number of ports on the two functional blocks. Then follow p lines, describing the signal mapping:On the i:th line is the port number of the block on the right side which should be connected to the i:th port of the block on the left side.
输入n个序列，每个序列有p项，每个序列的第i个数ai代表左边的 i 号接到了右边的ai号。
题解
对输入的序列求LIS即可，由于p<40000而且是多组测试数据，要用nlogn的算法。
4.洛谷【p1091】合唱队形
题目描述
N位同学站成一排，音乐老师要请其中的(N-K)位同学出列，使得剩下的K位同学排成合唱队形。
合唱队形是指这样的一种队形：设K位同学从左到右依次编号为1，2…，K，他们的身高分别为T1，T2，…，TK， 则他们的身高满足T1<…Ti+1>…>TK(1<=i<=K)。
你的任务是，已知所有N位同学的身高，计算最少需要几位同学出列，可以使得剩下的同学排成合唱队形。
输入输出格式
输入格式：
输入文件chorus.in的第一行是一个整数N(2<=N<=100)，表示同学的总数。第一行有n个整数，用空格分隔，第i个整数Ti(130<=Ti<=230)是第i位同学的身高(厘米)。
输出格式：
输出文件chorus.out包括一行，这一行只包含一个整数，就是最少需要几位同学出列。
输入输出样例
输入样例#1：
8
186 186 150 200 160 130 197 220
输出样例#1：
4
数据范围
对于50％的数据，保证有n<=20；
对于全部的数据，保证有n<=100。
题解
合唱队形要求的是先上升，再下降的最长子序列，如图:
状态设计：F[i]表示以i结尾的最长上升子序列，G[i]代表从i开始的最长下降子序列。
状态转移：F[i]=max{F[j+1]}(1<=j < i,A[j]< A[i]),G[i]=max{G[j]+1}(i< j<=n,A[j]< A[i])
边界处理：F[i]=1,G[i]=1(1<=i<=n)
最后的答案是ans=max{F[i]+G[i]-1}(1<=i<=n)
减1的原因是i重复算了两遍
代码：
#include <iostream>
#include <cstdio>
#include <algorithm>
using namespace std;
const int maxn =1001;
int a[maxn],f[maxn],g[maxn];
int n;
int main()
{
int ans=0,l;
scanf("%d",&n);
for(int i=1;i<=n;i++){
scanf("%d",&a[i]);
g[i]=f[i]=1;
}
for(int i=1;i<=n;i++){
for(int j=1;j<=i-1;j++)
if(a[j]<a[i]&&f[i]<f[j]+1)
f[i]=f[j]+1;
}
for(int i=n;i>=1;i--){
for(int j=n;j>=i+1;j--)
if(a[j]<a[i]&&g[i]<g[j]+1)
g[i]=g[j]+1;
}
for(int i=1;i<=n;i++)
ans=max(ans,f[i]+g[i]-1);
printf("%d\n",n-ans);
return 0;
}5.洛谷【p1439】排列LCS问题
题目描述
给出1-n的两个排列P1和P2，求它们的最长公共子序列。
输入输出格式
输入格式：
第一行是一个数n，
接下来两行，每行为n个数，为自然数1-n的一个排列。
输出格式：
一个数，即最长公共子序列的长度
输入输出样例
输入样例#1：
5
3 2 1 4 5
1 2 3 4 5
输出样例#1：
3
【数据规模】
对于50%的数据，n≤1000
对于100%的数据，n≤100000
题解
50分做法：直接跑LCS（最长公共子序列）
满分做法：
注意到题目中的两个序列都是1~n的一个排列。若其中一个排列是1,2,3…n，那么他们的LCS（最长公共子序列）就是就是另一个序列的LIS（最长上升子序列）。如果两个序列的排列都不是1,2,3…n，那么我们可以认为其中一个序列是1,2,3..n，然后把第一个序列的a[1]映射到1，a[2]映射到2，a[n]映射到n，对b序列也按照a序列的映射规则处理，这样再求b序列的LIS即可。
代码：
#include <iostream>
#include <cstdio>
#include <algorithm>
#include <cstdlib>
#include <cstring>
#include <cmath>
using namespace std;
const int maxn =100003,INF=0x7f7f7f7f;
int low[maxn];
int a[maxn],b[maxn];
int main()
{
int n,ans=1;
scanf("%d",&n);
for(int i=1;i<=n;i++)
{
int x;
scanf("%d",&x);
a[x]=i;//把a[i]映射到i
}
for(int i=1;i<=n;i++)
{
int x;
scanf("%d",&x);
b[i]=a[x];//把b数组按照a数组的映射规则进行映射
}
for(int i=1;i<=n;i++) low[i]=INF;//初始化
low[1]=b[1];
for(int i=2;i<=n;i++)
{
if(b[i]>=low[ans])
low[++ans]=b[i];
else
low[lower_bound(low+1,low+ans+1,b[i])-low]=b[i];//利用STL的lower_bound减少码量
}
printf("%d\n",ans);
return 0;
}后记
本人水平有限，本文如有错误，欢迎指正：）