【转载】动态规划算法3——最长上升子序列

https://www.cnblogs.com/sasuke-/p/5396843.html

今天我们要讲的是最长上升子序列（LIS）。

【题目描述】

给定N个数，求这N个数的最长上升子序列的长度。

【样例输入】

7

2 5 3 4 1 7 6

【样例输出】

4

什么是最长上升子序列？ 就是给你一个序列，请你在其中求出一段不断严格上升的部分，它不一定要连续。

就像这样：2,3,4,7和2,3,4,6就是序列2 5 3 4 1 7 6的两种选取方案。最长的长度是4.

那么，怎么求出它的最大上升子序列长度为4呢？这里介绍两种方法，都是以动态规划为基础的。

首先，我们先介绍较慢（O（n2n2））的方法。我们记num为到这个数为止，最长上升子序列的长度。

这种方法就是每一次寻找“可以接下去的”，换句话说，设原序列为a，则

当aj<ai(j<i)ajnumi时，numi=numj+1numi=numj+1。

对于每一个数，他都是在“可以接下去”的中，从前面的最优值+1转移而来。

因此，这个算法是可以求出正确答案的。复杂度很明显，外层i枚举每个数，内层j枚举目前i的最优值，即O（n2n2）。

那么，有没有更快的方法呢？当然有。这回要用到二分。

我们回想一下，在上面O（n2n2）的程序中，哪些地方看起来比较费时？

没错，就是内层用于更新i的循环。因为每一次他都要查找一遍，效率并不高。

回到题目，我们发现，他只要我们求长度，所以？

我们可以模拟一个栈。

所以每遇到一个比栈顶元素大的数，就放进栈里，遇到比栈顶元素小的就二分查找前边的元素，找到一个“最应该被换掉的元素”，用新数去更新前边的元素。

这个算法不难证明也是正确的。因为前面每一次的枚举都换成了二分，内层的复杂度从nn降到了log2log2，外层不变。所以总的复杂度是O(nlog2nnlog2n)。

接下来，我先给出朴素算法的代码。

#includeconstintMAX=1001;int a[MAX];intlis(int x)

{

    int num[MAX];

    for(inti=0;i

    {

        num[i]=1;

        for(intj=0;j

        {

            if(a[j]num[i])

                  num[i]=num[j]+1;

        }

    }

    intmaxx=0;

    for(inti=0;i

        if(maxx

            maxx=num[i];

    return maxx;

}int main()

{

    int n;

    scanf("%d",&n);

    for(inti=0;i

        scanf("%d",&a[i]);

    return!printf("%d\n",lis(n));

}

这个则是二分算法的代码：

#include#includeconstintMAXN=200001;int a[MAXN];int d[MAXN];int main()

{

    int n;

    scanf("%d",&n);

    for(inti=1;i<=n;i++)

        scanf("%d",&a[i]);

    d[1]=a[1];

    intlen=1;

    for(inti=2;i<=n;i++)

    {

        if(a[i]>d[len])

            d[++len]=a[i];

        else        {

            intj=std::lower_bound(d+1,d+len+1,a[i])-d;

            d[j]=a[i];

        }

    }

    printf("%d\n",len);   

    return0;

}

类似的，我们可以通过二分查找中改变“上确界”和“下确界”，以及符号（“<”和“<=”或“>”、“>=”等），求出最长不下降、不上升、严格下降子序列等问题。

希望对大家有帮助。满意请点赞！