最长单调上升子序列问题
请问下面两段代码的区别是什么
#include <bits/stdc++.h>
using namespace std;const int N = 1e5 + 5;
int a[N], x, n,m;
int g[N], cnt;int main() {cin>>m;while (m--) {cin>>x;a[++n] = x;}cnt = 0;g[0] = -2e9;for (int i = 1; i <= n; i++) {if (a[i] > g[cnt]) g[++cnt] = a[i];else {int l = 1, r = cnt;while (l < r) {int mid = l + r >> 1;if (g[mid] >=a[i]) r = mid;else l = mid + 1;}g[l] = a[i];}}cout << cnt << endl; // 最长上升子序列
}
#include <bits/stdc++.h>
using namespace std;const int N = 1e5 + 5;
int a[N], x, n,m;
int g[N], cnt;int main() {cin>>m;while (m--) {cin>>x;a[++n] = x;}cnt = 0;g[0] = -2e9;for (int i = 1; i <= n; i++) {if (a[i] > g[cnt]) g[++cnt] = a[i];else {int l = 1, r = cnt;while (l < r) {int mid = l + r >> 1;if (g[mid] >a[i]) r = mid;else l = mid + 1;}g[l] = a[i];}}cout << cnt << endl; // 最长上升子序列
}
为什么在求最长公共子序列时,f[mid]大于等于或大于a[i]都可以,而在最长单调上升子序列中只能大于等于,不能大于