最长递增子序列（LIS）的O（N^2）与O（NlogN）算法分析

最长递增子序列（LIS）的O（N^2）与O（NlogN）算法分析2014-07-14 csdn博客 synapse7题目：

求一个一维数组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;
}