首页 > 代码库 > 【最长上升子序列LIS】O(n^2)和O(nlogn)算法简记
【最长上升子序列LIS】O(n^2)和O(nlogn)算法简记
最长上升子序列(Longest Increasing Subsquence)是指对一个序列，其中满足i < j < k且a[i] < a[j] < a[k]的最长子序列a[]。比如1 4 2 6 3 7 9，则【1,2,3,7，9】就是它的LIS。
LIS普遍求法为动态规划。有两种算法。
第一种比较好写，复杂度O(n^2)。
设原序列为a[]。所有下标从1开始(即[1,n])。定义dp[i]为以a[i]结尾的最长上升子序列的长度。很容易得到转移方程：dp[i] = max{1, dp[j] + 1} 且 j < i。可以这么更新：
dp[i] = 1;
for (int j = 1; j < i; ++j) {
if (a[j] < a[i]) dp[i] = max(dp[i], dp[j] + 1);
}
这里选取poj2533来说明具体的实现。
#include <cstdio>
#include <cstring>
#include <algorithm>
using namespace std;
const int MAX = 1024;
const int INF = 0xfffffff;
int a[MAX];
int dp[MAX];
/*
dp[i]: 以a[i]为结尾的最长上升子序列的长度
*/
inline int read() {
char ch;
while ((ch = getchar()) < '0' || ch > '9');
int x = ch - '0';
while ((ch = getchar()) >= '0' && ch <= '9') {
x = (x << 3) + (x << 1) + ch - '0';
}
return x;
}
int main() {
int n;
while (~scanf(" %d", &n)) {
for (int i = 1; i <= n; ++i) {
a[i] = read();
}
int ans = 0;
for (int i = 1; i <= n; ++i) {
dp[i] = 1;
for (int j = 1; j < i; ++j) {
if (a[j] < a[i] && dp[j] + 1 > dp[i]) {
dp[i] = dp[j] + 1;
}
}
if (dp[i] > ans) ans = dp[i];
}
printf("%d\n", ans);
}
return 0;
}很多情况下这种解法达不到我们需要的复杂度，因为实际情形下动辄就是几百万的数据量。。。这时就需要改进上述算法
增加数组d[]，d[i]记录的是a[]数组中所有使得dp[j]=i的最小值。维护d[]使得d[]满足单调性（因为是上升子序列，这里就是单调增，如果求下降子序列扩展成单调减即可），另外维护一个值maxLen记录最长位置
举例如下(下标从1开始)：
对于序列a[] = {1,5,7,2,3,6,8}
初始化d[] = INF.即任意d[i]都等于一个很大的值，避免影响答案。maxLen = 0即可。
但是d[0] = -INF，下面说原因。
第一次：dp[1] = 1（长度为1）, maxLen = 1, d[1] = 1（最长上升子序列为1的最小结尾数字是a[1]，等于1），剩下的d[i]不变（下同）。此时d[] = {-INF, 1, INF, INF...INF}
第二次：a[2] = 5 > d[maxLen]。则dp[2] = maxLen + 1 = 2 (长度为2），maxLen = 2，d[2] = 5 （最长上升子序列为2的最小结尾数字是5）。d[] = {-INF, 1, 5, INF,...,INF}
第三次：a[3] = 7 > d[maxLen]，则dp[3] = maxLen + 1 = 3，maxLen = 3, d[3] = 7。此时d[] = {-INF, 1, 5, 7, INF, INF, INF...}
第四次：a[4] = 2 < d[maxLen]，则从d[1]到d[maxLen]中找最后一个比2小的数，找到数字1，下标为ind = 1(d[1] = 1嘛~)，dp[4] = dp[ind] + 1 = dp[1] + 1 = 2, maxLen为3不动, d[ind+1] = d[2] = 2。此时d[] = {-INF, 1, 2, 7, INF, INf, INf...}
第五次：a[5] = 3 < d[maxLen],则从d[1]到d[maxLen]找最后一个比3小的数，找到2，下标为ind = 2(d[2] = 2哦)，dp[5] = dp[ind] + 1 = dp[2] + 1 = 3, maxLen为3不动，d[ind+1] = d[3] = 3.此时{-INF, 1, 2, 3, INF, INF, INF...}
第六次：a[6] = 6 > d[maxLen]，直接dp[6] = maxLen + 1 = 4, maxLen = 4, d[4] = 6.此时d[] = {-INF, 1, 2, 3, 6, INF, INF...}
第七次：a[7] = 8 > d[maxLen], 直接dp[7] = maxLen + 1 = 4, maxLen = 5, d[5] = 8.此时d[] = {-INF, 1, 2, 3, 6, 8, INF, INF...}
上述就是更新过程，为什么d[0]要初始化为一个负无穷(-INF)呢？因为假设a[]都是正整数，之前记录的d[1] = 5.后面出来一个1，显然如果d[0]不是很小，就不好找所谓“比1小的最后一个数”了，没人比它小！！！
不过话说回来，找最后一个比它小的，更新值时又去更新的是后面一个数，那我们还不如找数组{d[1]到d[i]}中第一个比a[i]大的数呢！呵呵，就是这样的！
你不会到现在还没明白为什么要这么更新吧？我们大费周章让d[]单调递增，然后更新时刻意选择d[]中小于a[i]和大于a[i]的”交界点“，其实是为了可以使用二分搜索，从而加速整个算法呀！二分搜索可以达到O(logn)的复杂度，这样一来我们在更新时不需要遍历所有1<=j<i，只需要更新一个点，复杂度不就马上降下来了嘛！
还有，我们最后得到的答案不就是maxLen了嘛？还要dp[]数组作甚？对，如果只需要最长上升子序列的长度，这个dp数组就没用了。。。不过我还是习惯性地保留，万一用上了呢。。。
下面给出poj2533的实现：
#include <cstdio>
#include <cstring>
#include <algorithm>
using namespace std;
const int INF = 0xfffffff;
const int MAX = 1024;
int dp[MAX];
int a[MAX];
int d[MAX];
inline int read() {
char ch;
while ((ch = getchar()) < '0' || ch > '9');
int x = ch - '0';
while ((ch = getchar()) >= '0' && ch <= '9') {
x = (x << 3) + (x << 1) + ch - '0';
}
return x;
}
int main() {
int n;
while (~scanf(" %d", &n)) {
for (int i = 1; i <= n; ++i) {
a[i] = read();
//scanf(" %d", a + i);
}
//初始化
fill(d, d + n + 1, INF);
d[0] = -INF; //-INF必须小于所有的a[i]，否则可能影响算法，INF必须大于所有a[i]
dp[0] = 0;//下面说明初始化原因
int maxLen = 0;
for (int i = 1; i <= n; ++i) {
if (a[i] > d[maxLen]) {
//此时把a[i]加到末尾可以获得更长的子序列
//这里第一次迭代时必须被执行，我们必须保证a[1] > d[0]。这也是初始化d[0]=-INF的原因
maxLen++;
dp[i] = maxLen;
d[maxLen] = a[i];
} else {
int ind = upper_bound(d, d + maxLen + 1, a[i]) - d;//upper_bound找{d[0],..,d[maxLen]}第一个大于a[i]的数，注意下标
d[ind] = a[i];
dp[i] = dp[ind-1] + 1;//试想，这里可能找到ind=1，那么就变成dp[0]+1了， 所以dp[0]初始化为0
}
}
printf("%d\n", maxLen);
}
return 0;
}toj4071:#include <cstdio>
#include <cstring>
#include <algorithm>
using namespace std;
const int INF = 0xffffff;
const int MAX = 100007;
int a[MAX], d[MAX];
struct Node {
int x, y;
bool operator<(const Node& B)const {
return x == B.x ? y < B.y : x < B.x;
}
} bird[MAX];
inline int read() {
char ch;
while ((ch = getchar()) < '0' || ch > '9');
int x = ch - '0';
while ((ch = getchar()) >= '0' && ch <= '9') {
x = (x << 3) + (x << 1) + ch - '0';
}
return x;
}
int main() {
int T, n;
T = read();
//scanf(" %d", &T);
while (T--) {
n = read();
//scanf(" %d", &n);
for (int i = 1; i <= n; ++i) {
bird[i].x = read();
bird[i].y = read();
//scanf(" %d %d", &bird[i].x, &bird[i].y);
}
sort(bird + 1, bird + n + 1);
for (int i = 1; i <= n; ++i) {
a[i] = bird[i].y;
}
fill(d + 1, d + n + 1, INF);
int maxLen = 0, ind;
for (int i = 1; i <= n; ++i) {
if (a[i] >= d[maxLen]) {
++maxLen;
d[maxLen] = a[i];
} else {
ind = upper_bound(d + 1, d + maxLen + 1, a[i]) - d;
d[ind] = a[i];
}
}
printf("%d\n", maxLen);
}
return 0;
}【最长上升子序列LIS】O(n^2)和O(nlogn)算法简记