题目：
求一个一维数组arr[n]中的最长递增子序列的长度，如在序列1,5,8,3,6,7中，最长递增子序列长度为4 (即1,3,6,7)。
由于LIS用O(NlogN)也能打印，O(N^2)的DP方法见最后。
从LIS的性质出发，要想得到一个更长的上升序列，该序列前面的数必须尽量的小。
对于原序列1,5,8,3,6,7来说，当子序列为1,5,8时，遇到3时，序列已经不能继续变长了。但是，我们可以通过替换，使“整个序列”看上去更小，从而有更大的机会去变长。这样，当替换5-3和替换8-6完成后（此时序列为1,3,6），我们可以在序列末尾添加一个7了。
那为什么复杂度可以是O(NlogN)呢？
关键就在“替换”这一步上，若直接遍历序列替换，每次替换都要O(N)的时间。但是只要我们再次利用LIS的性质——序列是有序的（单调的），就可以用二分查找，在O(logN)的时间内完成一次替换，所以算法的复杂度是O(NlogN)的。
代码如下：
[cpp] view plaincopyprint?01.#include<bits/stdc++.h> 02.using namespace std; 03. 04.const int inf = 0x3f3f3f3f; 05.const int mx = int(1e5) + 5; 06. 07.int a[mx], dp[mx], pos[mx], fa[mx]; 08.vector<int> ans; 09. 10.int get_lis(int n) 11.{ 12. memset(dp, 0x3f, sizeof(dp)); 13. pos[0] = -1; 14. int i, lpos; 15. for (i = 0; i < n; ++i) 16. { 17. dp[lpos = (lower_bound(dp, dp + n, a[i]) - dp)] = a[i]; 18. pos[lpos] = i; /// *靠后打印 19. fa[i] = (lpos ? pos[lpos - 1] : -1); 20. } 21. n = lower_bound(dp, dp + n, inf) - dp; 22. for (i = pos[n - 1]; ~fa[i]; i = fa[i]) ans.push_back(a[i]); 23. ans.push_back(a[i]); /// 最后逆序打印ans即可 24. return n; 25.}
#include<bits/stdc++.h>using namespace std;const int inf = 0x3f3f3f3f;const int mx = int(1e5) + 5;int a[mx], dp[mx], pos[mx], fa[mx];vector<int> ans;int get_lis(int n){ memset(dp, 0x3f, sizeof(dp)); pos[0] = -1; int i, lpos; for (i = 0; i < n; ++i) { dp[lpos = (lower_bound(dp, dp + n, a[i]) - dp)] = a[i]; pos[lpos] = i; /// *靠后打印 fa[i] = (lpos ? pos[lpos - 1] : -1); } n = lower_bound(dp, dp + n, inf) - dp; for (i = pos[n - 1]; ~fa[i]; i = fa[i]) ans.push_back(a[i]); ans.push_back(a[i]); /// 最后逆序打印ans即可 return n;}
查看本栏目更多精彩内容：http://www.bianceng.cnhttp://www.bianceng.cn/Programming/sjjg/
以上是小编为您精心准备的的内容，在的博客、问答、公众号、人物、课程等栏目也有的相关内容，欢迎继续使用右上角搜索按钮进行搜索dp
， int
， 复杂度
， lis通讯
， 序列
， pos
， 递增子序列
， 逆序
， 最长递增子序列
， lis
， lis算法
， 递增序列
， O(N)算法
最长递增
最长递增子序列 nlogn、最长上升子序列 nlogn、最长公共子序列 nlogn、最长不降子序列 nlogn、最长递增子序列，以便于您获取更多的相关知识。