这是一篇由超级菜的OIer写的博客......
LIS就是最长上升子序列，通过DP求解。
普通的求法是\(O({n}^{2})\)的(相信大家都会写)：
解法1
#include <bits/stdc++.h>
using namespace std;
const int N = 105, inf = 1e9 + 10;
int a[N], f[N];
int n, ans = -inf;
int main() {
cin >> n;
for (int i = 1; i <= n; i ++) {cin >> a[i]; f[i] = 1;}
for (int i = 1; i <= n; i ++)
for (int j = 1; j < i; j ++)
if (a[i] > a[j]) f[i] = max(f[i], f[j] + 1);
for (int i = 1; i <= n; i ++)
ans = max(ans, f[i]);
cout << ans << '\n';
return 0;
}
n如果比较大，这种做法当然就不行了。
有一种基于贪心的二分求解方法，我们维护一个最长上升序列，扫描a[i], a[i]>序列末尾的数，加进去，序列长度+1；如果a[i] <=序列末尾，我们可以通过二分找到序列中第一个大等于a[i]的数，用a[i]替换掉它（相当于在不改变序列单调性的前提下使某一个数减小），这就是基于贪心思想的求法，最后序列的长度也就是我们要找的LIS。
解法2
#include <bits/stdc++.h>
using namespace std;
const int N = 1e5 + 10, inf = 1e9 + 10;
int f[N], a[N];
int n, ans;
int main() {
cin >> n;
for (int i = 1; i <= n; i ++) cin >> a[i], f[i] = inf;
f[1] = a[1];
ans = 1;//初始答案
for (int i = 2; i <= n; i ++) {
if (a[i] > f[ans]) f[++ ans] = a[i];
else f[lower_bound(f + 1, f + ans + 1, a[i]) - f] = a[i];
}
cout << ans << '\n';
}
这样复杂度就优化成\(O(nlogn)\)了。
还有没有其他做法呢？众所周知，算法的魅力有很大一部分在于寻找不断优化的过程，我们进一步分析DP过程，f[i] = max(f[j] + 1, f[i]) (a[j] < a[i], j < i),而我们每次更新f[i]时，都要枚举1~i-1的所有j,这是很大的浪费。我们可以用树状数组优化，
对于每个a[i]，查询它前面最大的f[j]，f[i] = f[j] + 1,再向树状数组a[i]位置中插入f[i]，该树状数组以值域为下标，维护的是最大的f[j]。复杂度同样是\(O(nlogn)\), 如果数值较大，记得离散化。
解法3
#include <bits/stdc++.h>
using namespace std;
const int N = 1e5 + 10;
int n, c[N], f[N], a[N];
void add(int x, int y) {
while (x < N) {
c[x] = max(c[x], y);
x += x & (-x);
}
}
int query(int x) {
int res = 0;
while(x) {
res = max(res, c[x]);
x -= x & (-x);
}
return res;
}
signed main() {
cin >> n;
for (int i = 1; i <= n; i ++) cin >> a[i];
for (int i = 1; i <= n; i ++) {
f[i] = query(a[i]) + 1;
add(a[i], f[i]);
}
int ans = 0;
for (int i = 1; i <= n; i ++) ans = max(ans, f[i]);
cout << ans << '\n';
}
LCS最长公共子序列。给你两个序列，求他们的最长公共部分。
常规解法：
#include <bits/stdc++.h>
using namespace std;
const int N = 5010;
int a[N], b[N], f[N][N], n, m;
int main() {
cin >> n >> m;
for (int i = 1; i <= n; i ++) cin >> a[i];
for (int i = 1; i <= m; i ++) cin >> b[i];
for (int i = 1; i <= n; i ++) {
for (int j = 1; j <= m; j ++) {
f[i][j] = max(f[i - 1][j], f[i][j - 1]);
if (a[i] == b[j]) f[i][j] = max(f[i][j], f[i - 1][j - 1] + 1);
}
}
cout << f[n][m];
}
n较大时这种解法肯定不能用了，此时题目应该还会给其他条件。
看一道题：
P1439 【模板】最长公共子序列
两个序列是相同长度n，且其中的元素范围都是1~n，观察n可以取到\(10 ^ 5\),那么上面的方法肯定不能用，我们可以将a序列每个元素映射为编号，这样a序列就是1~n，对于b采用a的映射方式，问题就转化为了求b的最长上升子序列了，采用二分的方式。
代码：
#include <bits/stdc++.h>
using namespace std;
const int N = 1e5 + 10, inf = 1e9 + 10;
int n, a[N], b[N], mp[N], f[N];
int main() {
cin >> n;
for (int i = 1; i <= n; i ++) {cin >> a[i]; mp[a[i]] = i;}
for (int i = 1; i <= n; i ++) {cin >> b[i]; f[i] = inf;}
int len = 0;
for (int i = 1; i <= n; i ++) {
if (mp[b[i]] > f[len]) f[++ len] = mp[b[i]];
else f[lower_bound(f + 1, f + len + 1, mp[b[i]]) - f] = mp[b[i]];
//找f数组中第一个>=mp[b[i]]的位置。
}
cout << len << '\n';
return 0;
}