在计算机科学中，最长递增子序列（longest increasing subsequence）问题是指，在一个给定的数值序列中，找到一个子序列，使得这个子序列元素的数值依次递增，并且这个子序列的长度尽可能地大。最长递增子序列中的元素在原序列中不一定是连续的
– 维基百科
如
1 3 4 2 5
则最长递增子序列为
1 3 4
或
1 3 5
或
1 4 5
，长度都为3。
DP解法 - O(n*n)
设dp[i]为arr[i]为结尾的LIS长度，则显然
dp[i] = max{dp[j] + 1 } , j < i && arr[j] < arr[i]
注意下初始情况下dp[i]为1，然后代码就easy了
const int maxn = 1000;
const int inf = 0x7f;
int lis_dp(int *arr, int n) {
int dp[maxn];
int ans = 1;
for (int i = 0; i < n; ++i) {
dp[i] = 1;
for (int j = 0; j < i; ++j) {
if (arr[i] > arr[j] && dp[i] < dp[j] + 1) {
dp[i] = dp[j] + 1;
}
}
if (dp[i] > ans)
ans = dp[i];
}
return ans;
}
O(n*log(n))解法
我们发现上面的第二层循环只是找个max(dp[j])，那么就可以用二分优化，但不是直接的把第二个循环换成二分查找，直接看代码。
定义数组
f[i]:以arr[i]结尾的lis长度
g[i]:长度为i的lis的最后个数字，长度相同时取最小的结尾数字
其中的g[i]在相同长度时，比如
1 3 4 2 5
的LIS为
1 3 4
或
1 3 5
或
1 4 5
，则g[3]为4，因为显然长度相等情况下最后个数字更小更好。
int lis(int *arr, int n) {
int f[maxn],g[maxn];
int ans = 1;
memset(g, inf, sizeof(g));
for (int i = 0; i < n; ++i) {
f[i] = lower_bound(g + 1, g + 1 + n, arr[i]) - g;
g[f[i]] = arr[i];
ans = max(f[i], ans);
}
return ans;
}
关键在于
lower_bound
的参数+1和返回值，我们遍历每个数字的时候在g[]里取>=arr[i]的第一个位置，这个位置(从1开始计数的话)就是以arr[i]结尾的LIS的长度(即f[i])，且当前这个数字也是这个长度下的g值(即g[f[i]])。
上个例子看看
n = 5
arr[]: 10 30 15 20 60
f[]: 1 2 2 3 4
g[f[]]: 10 30 15 20 60
带着f和g的定义去想代码流程就容易想通的，这里不具体分析了，下面给一些关键点
-
lower_bound
-
lower_bound
转为LCS - O(n*n)
我们可以将原数组复制一份，然后对新数组排序，之后求原数组和新数组的LCS（最长公共子序列）即是答案，复杂度O(nn)，也需要开个nn的空间，比较伤。
int lis_lcs(int *arr, int n) {
int cp[maxn];
memcpy(cp, arr, sizeof(int)*n);
sort(cp, cp + n);
int dp[maxn][maxn];
memset(dp, 0, sizeof(dp));
for (int i = 1; i <= n; ++i) {
for (int j = 1; j <= n; ++j) {
if (arr[i - 1] == cp[j - 1]) { //注意下标对应关系
dp[i][j] = dp[i - 1][j - 1] + 1;
} else {
dp[i][j] = max(dp[i - 1][j], dp[i][j - 1]) ;
}
}
}
return dp[n][n];
}
题目
POJ 2533 裸LIS 两种解法都能过
HDU 5748 Bellovin - BC 84期B题
给一个序列A，要求找出另外个序列B，符合每个以B[i]结尾的LIS都和A[i]的一样且序列B是所有解中字典序最小的。
你会发现 序列A的LIS数组本身就是答案，它的长度代表了字典序最小。