凡科建站视频教程,南宁网站设计推荐,如何提升网站流量,扁平化 wordpress今天我们要讲的是最长上升子序列#xff08;LIS#xff09;。【题目描述】给定N个数#xff0c;求这N个数的最长上升子序列的长度。【样例输入】 【样例输出】7 42 5 3 4 1 7 6那么什么是最长上升子序列呢#xff1f; 就是给你一个序列…今天我们要讲的是最长上升子序列LIS。【题目描述】给定N个数求这N个数的最长上升子序列的长度。【样例输入】 【样例输出】7 42 5 3 4 1 7 6那么什么是最长上升子序列呢 就是给你一个序列请你在其中求出一段不断严格上升的部分它不一定是要连续的。 就像这样2,3,4,7和2,3,4,6就是序列2 5 3 4 1 7 6的两种选取方案这个数列的最长长度是4. 那么怎么求出它的最大上升子序列长度为4呢这里介绍两种方法都是以动态规划为基础的。 首先我们先介绍较慢On2的方法。我们记num为到这个数为止时的最长上升子序列的长度。 这种方法就是每一次寻找“可以接下去的”换句话说设原序列为a则 当ajai(ji)且numj1numi时numinumj1。 对于每一个数他都是在“可以接下去”的中从前面的最优值1转移而来。 因此这个算法是可以求出正确答案的。 复杂度很明显外层i枚举每个数内层j枚举目前i的最优值即On2。 那么有没有更快的方法呢当然有。这回要用到二分。 我们回想一下在上面On2的程序中哪些地方看起来比较费时 没错就是内层用于更新i的循环。因为每一次它都要查找一遍效率并不高。 回到题目我们发现他只要我们求长度所以…… 我们可以模拟一个栈。每遇到一个比栈顶元素大的数就放进栈里遇到比栈顶元素小的就二分查找前边的元素找到一个“最应该被换掉的元素”用新数去更新前边的元素。 这个算法不难证明也是正确的。因为前面每一次的枚举都换成了二分内层的复杂度从n降到了log2外层不变。所以总的复杂度是O(nlog2n)。 接下来我先给出朴素算法的代码。 1 #includecstdio2 const int MAX1001;3 int a[MAX];4 int lis(int x)5 {6 int num[MAX];7 for(int i0;ix;i)8 {9 num[i]1;
10 for(int j0;ji;j)
11 {
12 if(a[j]a[i]num[j]1num[i])
13 num[i]num[j]1;
14 }
15 }
16 int maxx0;
17 for(int i0;ix;i)
18 if(maxxnum[i])
19 maxxnum[i];
20 return maxx;
21 }
22 int main()
23 {
24 int n;
25 scanf(%d,n);
26 for(int i0;in;i)
27 scanf(%d,a[i]);
28 return !printf(%d\n,lis(n));
29 } 这个则是二分算法的代码 1 #includecstdio2 #includealgorithm3 const int MAXN200001;4 5 int a[MAXN];6 int d[MAXN];7 8 int main()9 {
10 int n;
11 scanf(%d,n);
12 for(int i1;in;i)
13 scanf(%d,a[i]);
14 d[1]a[1];
15 int len1;
16 for(int i2;in;i)
17 {
18 if(a[i]d[len])
19 d[len]a[i];
20 else
21 {
22 int jstd::lower_bound(d1,dlen1,a[i])-d;
23 d[j]a[i];
24 }
25 }
26 printf(%d\n,len);
27 return 0;
28} 类似的我们可以通过二分查找中改变“上确界”和“下确界”以及符号“”和“”或“”、“”等求出最长不下降、不上升、严格下降子序列等问题。 由于作者也正在学习中这篇文章只是借用别人的文章并加上自己的理解。 原文http://www.cnblogs.com/frankchenfu/转载于:https://www.cnblogs.com/zhengyongle506/p/10554208.html
