动态规划算法——最长上升子序列

今天我们要讲的是最长上升子序列（LIS）。
【题目描述】
给定N个数，求这N个数的最长上升子序列的长度。
【样例输入】　　　　【样例输出】
7 　　　　　　4
2 5 3 4 1 7 6

那么什么是最长上升子序列呢？
就是给你一个序列，请你在其中求出一段不断严格上升的部分，它不一定是要连续的。
就像这样：2,3,4,7和2,3,4,6就是序列2 5 3 4 1 7 6的两种选取方案，这个数列的最长长度是4.

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

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

这种方法就是每一次寻找“可以接下去的”，换句话说，设原序列为a，则
　　当aj<ai(j<i)且numj+1>numi时，numi=numj+1。
对于每一个数，他都是在“可以接下去”的中，从前面的最优值+1转移而来。
因此，这个算法是可以求出正确答案的。

复杂度很明显，外层i枚举每个数，内层j枚举目前i的最优值，即O（n2）。

那么，有没有更快的方法呢？当然有。这回要用到二分。
我们回想一下，在上面O（n2）的程序中，哪些地方看起来比较费时？
没错，就是内层用于更新i的循环。因为每一次它都要查找一遍，效率并不高。
回到题目，我们发现，他只要我们求长度，所以……？
我们可以模拟一个栈。
每遇到一个比栈顶元素大的数，就放进栈里，遇到比栈顶元素小的就二分查找前边的元素，找到一个“最应该被换掉的元素”，用新数去更新前边的元素。
这个算法不难证明也是正确的。因为前面每一次的枚举都换成了二分，内层的复杂度从n降到了log2，外层不变。所以总的复杂度是O(nlog2n)。

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

 1 #include<cstdio>
 2     const int MAX=1001;
 3     int a[MAX];
 4     int lis(int x)
 5     {
 6         int num[MAX];
 7         for(int i=0;i<x;i++)
 8         {
 9             num[i]=1;
10             for(int j=0;j<i;j++)
11             {
12                 if(a[j]<a[i]&&num[j]+1>num[i])
13                        num[i]=num[j]+1;
14             }
15         }
16         int maxx=0;
17         for(int i=0;i<x;i++)
18             if(maxx<num[i])
19                 maxx=num[i];
20         return maxx;
21     }
22     int main()
23     {
24         int n;
25         scanf("%d",&n);
26         for(int i=0;i<n;i++)
27             scanf("%d",&a[i]);
28         return !printf("%d\n",lis(n));
29     }

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

 1 #include<cstdio>
 2 #include<algorithm>
 3 const int MAXN=200001;
 4     
 5 int a[MAXN];
 6 int d[MAXN];
 7     
 8 int main()
 9 {
10　　int n;
11　　scanf("%d",&n);
12　　for(int i=1;i<=n;i++)
13  　　  scanf("%d",&a[i]);
14　　d[1]=a[1];
15　　int len=1;
16　　for(int i=2;i<=n;i++)
17　　{
18　　　　if(a[i]>d[len])
19　　　　　　d[++len]=a[i];
20　　　　else
21　　　　　　{
22　　　　　　　　int j=std::lower_bound(d+1,d+len+1,a[i])-d;
23　　　　　　　　d[j]=a[i]; 
24　　　　　　}
25　　}
26　　printf("%d\n",len);    
27　　return 0;
28}

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

由于作者也正在学习中，这篇文章只是借用别人的文章并加上自己的理解。

原文：http://www.cnblogs.com/frankchenfu/

动态规划算法——最长上升子序列

推荐阅读