题解 AT2827 【LIS】

· · 题解

hello，大家好 ，我是库里的球迷

Emm..别闹了，开始说正题吧

列位看官留意，LIS（Longest Increasing Subsequence，最长上升子序列）是dp（也就是动态规划）算法的非常经典也非常常见，常考的应用。

下面我们来了解一下LIS：

最长上升子序列（Longest  Increasing Subsequence），简称LIS，也有些情况求的是最长非降序子序列，二者区别就是序列中是否可以有相等的数。假设我们有一个序列 b i，当b1 < b2 < … < bS的时候，我们称这个序列是上升的。对于给定的一个序列(a1, a2, …, aN)，我们也可以从中得到一些上升的子序列(ai1, ai2, …, aiK)，这里1 <= i1 < i2 < … < iK <= N，但必须按照从前到后的顺序。比如，对于序列(1, 7, 3, 5, 9, 4, 8)，我们就会得到一些上升的子序列，如(1, 7, 9), (3, 4, 8), (1, 3, 5, 8)等等，而这些子序列中最长的（如子序列(1, 3, 5, 8) ），它的长度为4，因此该序列的最长上升子序列长度为4。

额，真抽象，我给你们解释一下

首先需要知道，子串和子序列的概念，我们以字符子串和字符子序列为例，更为形象，也能顺带着理解字符的子串和子序列：

  1. 字符子串指的是字符串中连续的n个字符，如abcdefg中，ab，cde，fg等都属于它的字串。
  2. 字符子序列指的是字符串中不一定连续但先后顺序一致的n个字符，即可以去掉字符串中的部分字符，但不可改变其前后顺序。如abcdefg中，acdg，bdf属于它的子序列，而bac，dbfg则不是，因为它们与字符串的字符顺序不一致。

知道了这个，数值的子序列就很好明白了，即用数组成的子序列。这样的话，最长上升子序列也很容易明白了，归根结底还是子序列，然后子序列中，按照上升顺序排列的最长的就是我们最长上升子序列了，这样听来是不是就很容易明白啦～

 还有一个非常重要的问题：请大家用集合的观点来理解这些概念，子序列、公共子序列以及最长公共子序列都不唯一，但很显然，对于固定的数组，虽然LIS序列不一定唯一，但LIS的长度是唯一的。再拿我们刚刚举的栗子来讲，给出序列 ( 1, 7, 3, 5, 9, 4, 8)，易得最长上升子序列长度为4,这是确定的，但序列可以为 ( 1, 3, 5, 8 ), 也可以为 ( 1, 3, 5, 9 )。

说了半天，到底应该怎么求LIS的长度呢？

这里详细介绍一下求LIS的三种方法，分别是O(n^2)的DP，O(nlogn)的二分+贪心法，以及O(nlogn)的树状数组优化的DP。

一、算法一【动态规划】

我们都知道，动态规划的一个特点就是当前解可以由上一个阶段的解推出， 由此，把我们要求的问题简化成一个更小的子问题。子问题具有相同的求解方式，只不过是规模小了而已。最长上升子序列就符合这一特性。我们要求n个数的最长上升子序列，可以求前n-1个数的最长上升子序列，再跟第n个数进行判断。求前n-1个数的最长上升子序列，可以通过求前n-2个数的最长上升子序列……直到求前1个数的最长上升子序列，此时LIS当然为1。

让我们举个例子：求 2 7 1 5 6 4 3 8 9 的最长上升子序列。我们定义d(i) (i∈[1,n])来表示前i个数以A[i]结尾的最长上升子序列长度。

d(i)=max{d(1),d(2),……,d(i)} 我们可以看出这9个数的LIS为d(9)=5

总结一下，d(i)就是找以A[i]结尾的，在A[i]之前的最长上升子序列+1，当A[i]之前没有比A[i]更小的数时，d(i)=1。所有的d(i)里面最大的那个就是最长上升子序列。其实说的通俗点，就是每次都向前找比它小的数和比它大的数的位置，将第一个比它大的替换掉，这样操作虽然LIS序列的具体数字可能会变，但是很明显LIS长度还是不变的，因为只是把数替换掉了，并没有改变增加或者减少长度。但是我们通过这种方式是无法求出最长上升子序列具体是什么的，这点和最长公共子序列不同。

明白了？尝试程序表达一下吧，要注意初始化。

思考完后再看呦

#include<bits/stdc++.h>
using namespace std;

int n,ans;
int a[200010],dp[200010]={1}; //初始化
int main() {
    cin>>n;
    for(int i=1; i<=n; i++) cin>>a[i];
    for(int i=1; i<=n; i++) {
        dp[i]=1;
        for(int j=1; j<i; j++)
            if(a[i]>a[j] && dp[i]<dp[j]+1)  //判断
                dp[i]=dp[j]+1;
        ans=max(ans,dp[i]);
    }
    cout<<ans;
    return 0;
}

O(n^2),太大，100000数据有点吃力。。。

二、【算法二】 贪心+二分

新建一个 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)。

我们再举一个例子：有以下序列A[ ] = 3 1 2 6 4 5 10 7，求LIS长度。

我们定义一个B[ i ]来储存可能的排序序列，len 为LIS长度。我们依次把A[ i ]有序地放进B[ i ]里。

（为了方便，i的范围就从1~n表示第i个数）

最终我们得出LIS长度为5，但是，但是！！！B[ ] 中的序列并不一定是正确的最长上升子序列。 在这个例子中，我们得到的1 2 4 5 7 恰好是正确的最长上升子序列，下面我们再举一个例子：

有以下序列A[ ] = 1 4 7 2 5 9 10 3，求LIS长度。

最终我们得出LIS长度为5。但是，但是！！这里的1 2 3 9 10很明显并不是正确的最长上升子序列。因此，B序列并不一定表示最长上升子序列，它只表示相应最长子序列长度的排好序的最小序列。这有什么用呢？我们最后一步3替换5并没有增加最长子序列的长度，而这一步的意义，在于记录最小序列，代表了一种“最可能性”，只是此种算法为计算LIS而进行的一种替换。假如后面还有两个数据12和15，那么B[ ]将继续更新。

因为在B中插入的数据是有序的，不需要移动，只需要替换，所以可以用二分查找插入的位置，那么插入n个数的时间复杂度为〇(logn)，这样我们会把这个求LIS长度的算法复杂度降为了〇(nlogn)。

如果还有些迷迷糊糊，一起来看代码吧！


#include <cstdlib>
#include <cstring>
#include <iostream>
#include <algorithm>
using namespace std;

const int maxn =100010, 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;
}

这其中用到了二分查找第一个大于等于的，其实C++里面的有一个函数可用代替二分，那就是 —— low_bound( )函数。

下面是使用lower_bound优化最长上升子序列。由于长度相同的上升子序列只需要保存结尾最小的那个，而长度递增时，结尾数字的大小也是递增的。最长上升子序列就是找出比他大的第一个数。前面的数都比他小，所以他和这个数的长度相同。然后由于他比较然后小，更新找到的那个值。

#include<bits/stdc++.h>
using namespace std;
int n, ans;
int a[200010];
int f[200010]={-0x7f7f7f7f};

int main() {
    cin>>n;
    for(int i=1;i<=n;i++) cin>>a[i];
    for(int i=1;i<=n;i++) {
        int temp=lower_bound(f,f+ans+1,a[i])-f;
        f[temp]=a[i];
        if(ans<temp) ans=temp;
    }
    cout<<ans;
    return 0;
}

/*这个算法其实已经不是DP了，有点像贪心。至于复杂度降低其实是因为这个算法里面用到了二分搜索。
本来有N个数要处理是O(n)，每次计算要查找N次还是O(n)，一共就是O(n^2)；
现在搜索换成了O(logn)的二分搜索，总的复杂度就变为O(nlogn)了。
这里主要注意一下lower_bound函数的应用，注意减去的g是地址。
地址 - 地址 = 下标 。*/

三、【算法三】 树状数组维护 我们再来回顾O(n^2)DP的状态转移方程：

F [ i ] = max { F [ j ] + 1 ，F [ i ] } (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数组已经是有序的，所以可以直接更新。有点绕，具体看代码。

还有一点需要注意：树状数组求LIS不去重的话就变成了最长不下降子序列了。

#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;
}

注意，不要复制，我只是让大家看一下思路，提交上去会RE的！！你可以试试看

好了，讲了这么多，LIS也讲透了，如果喜欢的话点个赞吧！