数据结构与算法随笔之------动态规划问题之------最长上升子序列（LIS）问题（一文搞懂最长上升子序列（LIS））_用两分法最长上升子序列

LIS

（最长上升子序列（计算机科学））

定义：最长上升子序列（Longest Increasing Subsequence，LIS），在计算机科学上是指一个序列中最长的单调递增的子序列。

这里借鉴一个大佬的博客：https://www.cnblogs.com/GodA/p/5180560.html

方法1：枚举法（也就是动态规划）

我们都知道，动态规划的一个特点就是当前解可以由上一个阶段的解推出， 由此，把我们要求的问题简化成一个更小的子问题。子问题具有相同的求解方式，只不过是规模小了而已。最长上升子序列就符合这一特性。我们要求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]结尾的最长上升子序列长度。

　　前1个数 d(1)=1 子序列为2（A[i]=2)

　　前2个数 7前面有2小于7 d(2)=d(1)+1=2 子序列为2 7（A[i]=7)

　　前3个数 在1前面没有比1更小的，1自身组成长度为1的子序列 d(3)=1 子序列为1（A[i]=1)

　　前4个数 5前面有2小于5 d(4)=d(1)+1=2 子序列为2 5（A[i]=5)

　　前5个数 6前面有2 5小于6 d(5)=d(4)+1=3 子序列为2 5 6（A[i]=6)

　　前6个数 4前面有2小于4 d(6)=d(1)+1=2 子序列为2 4（A[i]=4)

　　前7个数 3前面有2小于3 d(3)=d(1)+1=2 子序列为2 3（A[i]=3)

　　前8个数 8前面有2 5 6小于8 d(8)=d(5)+1=4 子序列为2 5 6 8（A[i]=8)

　　前9个数 9前面有2 5 6 8小于9 d(9)=d(8)+1=5 子序列为2 5 6 8 9（A[i]=9)

　　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)里面最大的那个就是最长上升子序列。

       给个图大概就是：

具体实现代码如下：

#include<cstdio>
const int MAX=1001;
int a[MAX];
int lis(int x)
{
    int num[MAX];
    for(int i=0;i<x;i++)
    {
        num[i]=1;//用来子序列统计长度
        for(int j=0;j<i;j++)
        {
            if(a[j]<a[i]&&num[j]+1>num[i])//满足向后找且前面存的序列的长度加一比现在的大（也就是说可以往后找）（其实就是再找num[j]+1的最大值）
                   num[i]=num[j]+1;//那就把num里最长的加一后赋值过来
        }
    }
    int maxx=0;
    for(int i=0;i<x;i++)
        if(maxx<num[i])
            maxx=num[i];
    return maxx;
}
int main()
{
    int n;
    scanf("%d",&n);
    for(int i=0;i<n;i++)
        scanf("%d",&a[i]);
    printf("%d\n",lis(n));
    return 0;
}

这个算法的时间复杂度为〇(n²)，并不是最优的算法。在限制条件苛刻的情况下，这种方法行不通。那么怎么办呢！有没有时间复杂度更小的算法呢？说到这里了，当然是有的啦！还有一种时间复杂度为〇(nlogn)的算法，下面就来看看。

方法二：二分法

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

　　我们定义一个B[i]来储存可能的排序序列，len为LIS长度。我们依次把A[i]有序地放进B[i]里。（为了方便，i的范围就从1~n表示第i个数）

　　A[1]=3，把3放进B[1]，此时B[1]=3，此时len=1，最小末尾是3

　　A[2]=1，因为1比3小，所以可以把B[1]中的3替换为1，此时B[1]=1，此时len=1，最小末尾是1

　　A[3]=2，2大于1，就把2放进B[2]=2，此时B[]={1,2}，len=2

　　同理，A[4]=6，把6放进B[3]=6，B[]={1,2,6}，len=3

　　A[5]=4，4在2和6之间，比6小，可以把B[3]替换为4，B[]={1,2,4}，len=3

　　A[6]=5，B[4]=5，B[]={1,2,4,5}，len=4 

　　A[7]=10，B[5]=10，B[]={1,2,4,5,10}，len=5

　　A[8]=7，7在5和10之间，比10小，可以把B[5]替换为7，B[]={1,2,4,5,7}，len=5

　　最终我们得出LIS长度为5。但是，但是！！这里的1 2 4 5 7很明显并不是正确的最长上升子序列。是的，B序列并不表示最长上升子序列，它只表示相应最长子序列长度的排好序的最小序列。这有什么用呢？我们最后一步7替换10并没有增加最长子序列的长度，而这一步的意义，在于记录最小序列，代表了一种“最可能性”。假如后面还有两个数据8和9，那么B[6]将更新为8，B[7]将更新为9，len就变为7。读者可以自行体会它的作用。

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

      大致思路就是：我们可以用数组模拟栈。所以每遇到一个比栈顶元素大的数，就放进栈里。遇到比栈顶元素小的就二分查找前边的元素，找到一个“最应该被换掉的元素”（即数组中第一个大于等于key的元素），用新数去更新前边的元素（赋值）。

#include<cstdio>
#include<algorithm>
#include <bits/stdc++.h>
const int MAXN=200001;
 
int a[MAXN];
int d[MAXN];
int find(int a[],int start,int end,int key)//二分查找，返回a数组中第一个>=key的位置
{
    int left = start;
    int right = end;
    int mid;
    while(left <= right)
    {
        mid=(left + right)/2;
        if(d[mid] > key)
            right = mid - 1;
        else
            left = mid + 1;
    }
    return left;
}
 
int main()
{
    int n;
    scanf("%d",&n);
    for(int i=0;i<n;i++)
        scanf("%d",&a[i]);
    d[0]=a[0];//代表下标都从0开始
    int len=0;
    for(int i=0;i<n;i++)//用数组模拟栈
    {
        if(a[i]>=d[len])//每遇到一个比栈顶元素大的数，就放进栈里，
            d[++len]=a[i];
        else//遇到比栈顶元素小的就二分查找前边的元素
        {
            //int j=std::lower_bound(d+1,d+len+1,a[i])-d;//找到下标
            int j = find(a,1,len,a[i]);//返回第一个大于等于key的元素
            d[j]=a[i];//并用它替换掉栈顶元素
            //if(len < j)
                //len = j;
        }
    }
    printf("%d\n",len);
    return 0;
}

当然这里头把下标改为从1开始可能更直观些，此时代码如下代码

 
#include<cstdio>
#include<algorithm>
#include <bits/stdc++.h>
const int MAXN=200001;
 
int a[MAXN];
int d[MAXN];
int find(int a[],int start,int end,int key)//二分查找，返回a数组中第一个>=key的位置
{
    int left = start;
    int right = end;
    int mid;
    while(left <= right)
    {
        mid=(left + right)/2;
        if(d[mid] > key)
            right = mid - 1;
        else
            left = mid + 1;
    }
    return left;
}
 
int main()
{
    int n;
    scanf("%d",&n);
    for(int i=1;i<=n;i++)
        scanf("%d",&a[i]);
    d[1]=a[1];//代表下标都从0开始
    int len=1;
    for(int i=2;i<=n;i++)//用数组模拟栈
    {
        if(a[i]>=d[len])//每遇到一个比栈顶元素大的数，就放进栈里，
            d[++len]=a[i];
        else//遇到比栈顶元素小的就二分查找前边的元素
        {
            //int j=std::lower_bound(d+1,d+len+1,a[i])-d;//找到下标
            int j = find(a,1,len,a[i]);//返回第一个大于等于key的元素
            d[j]=a[i];//并用它替换掉栈顶元素
            //if(len < j)
                //len = j;
        }
    }
    printf("%d\n",len);
    return 0;
}

此外本题二分法的实现还可以使用stl的容器及函数

补充两种用stl的方法:

原理：

Set不但自动排序，里面还有upper_bound(num)函数，查找与num最接近的比num大的数，省去了内层循环,时间复杂度缩小到了O(n)。

#include <bits/stdc++.h>
using namespace std;
int main()
{
    int num,n;
    cin>>n;
    set<int> s;
    for(int i=0;i<n;i++)
    {
        cin>>num;
        if(s.upper_bound(num)!=s.end())//如果找到了最接近num且比num大的数（==s.end代表没找到）
            s.erase(s.upper_bound(num));//就把那个数删了（num照常插入）（更新过程）
        s.insert(num);
    }
    cout<<s.size();
    return 0;
}

或者使用lower_bound( begin,end,num)函数

在从小到大的排序数组中，

lower_bound( begin,end,num)：从数组的begin位置到end-1位置二分查找第一个大于或等于num的数字，找到返回该数字的地址，不存在则返回end。通过返回的地址减去起始地址begin,得到找到数字在数组中的下标。

upper_bound( begin,end,num)：从数组的begin位置到end-1位置二分查找第一个大于num的数字，找到返回该数字的地址，不存在则返回end。通过返回的地址减去起始地址begin,得到找到数字在数组中的下标。

关于它的使用方法可参考链接：https://blog.csdn.net/weixin_42110638/article/details/83412189

#include<cstdio>
#include<algorithm>
const int MAXN=200001;
 
int a[MAXN];
int d[MAXN];
 
int main()
{
    int n;
    scanf("%d",&n);
    for(int i=1;i<=n;i++)
        scanf("%d",&a[i]);
    d[1]=a[1];
    int len=1;
    for(int i=2;i<=n;i++)
    {
        if(a[i]>d[len])
            d[++len]=a[i];
        else
        {
            int j=std::lower_bound(d+1,d+len+1,a[i])-d;
            d[j]=a[i]; 
        }
    }
    printf("%d\n",len);    
    return 0;
}