最长公共子序列LCS和 最长单调子序列 及其二分优化

最长公共子序列LCS和最长上升子序列LIS都是动态规划的经典例题，再度回顾这两个例题，已经有了更深一些的理解和优化方式。

这里系统整理一下 。

最朴素的dp思路，就是对一个序列a[i]，设一个dp数组, 其中dp[i]的含义为以a[i]结尾的最长上升子序列的长度。

那么我们考虑当前的a[i]与与a[i]之前的元素的关系，

如果当前的a[i]与a[i]之前的a[j]满足递增关系，那么dp[i]的状态可以由dp[j]得到，对每个先前状态取最值即为当前状态的最优解。

有状态转移：

a[j] )" src="https://latex.codecogs.com/gif.latex?if%20%28a%5Bi%5D%20%3E%20a%5Bj%5D%20%29" />

对于边界问题，我们可以知道，一个元素他本身就是有序的，所以初始化所有状态为 1

#include 
#include
#include
#include
#include
#include
#include 
#include
using namespace std;
int n;
int arr[10000] = { 0 };
int dp[10000]= { 0 };//以arr[i]结尾的子列长为dp[i]

int main() {
	cin >> n;
	for (int j = 1; j <= n; j++) {
		cin >> arr[j];
		dp[j] = 1;
	}
	for (int j = 1; j <= n; j++) {
		for (int i = 1; i arr[i]) {
				dp[j] = max(dp[i] + 1, dp[j]);
			}
		}
	}
	int ans = 0;
	for (int j = 1; j <= n; j++) {//遍历找出最长上升序列
		ans = max(dp[j], ans);
	}
	cout << ans;
}

这是常规且比较暴力的LIS写法，时间复杂度为O(n^2),如果数据一大就不行了。

如本题数据为1e5。

但是我们可以很方便的输出找到的最长上升子序列，利用链式路径数组。

#include
using namespace std;
int n;
int arr[10000] = { 0 };
int dp[10000] = { 0 };//以arr[i]结尾的子列长为dp[i]
vector path(10001,-1);
int main() {
	
	cin >> n;
	for (int j = 1; j <= n; j++) {
		cin >> arr[j];
		dp[j] = 1;
	}
	for (int j = 1; j <= n; j++) {
		int pos = -1;//注意标记为-1，如果没有进行下面的遍历默认没有先前的状态
		for (int i = 1; i < j; i++) {
			if (arr[j] > arr[i]) {
				if (dp[j] < dp[i] + 1) {
					pos = i;
					dp[j] = dp[i] + 1;
				}
			}
		}
		path[j] = pos;//j是由i推来的,逆推
	}
	int ans = 0;
	int pos = 0;
	for (int j = 1; j <= n; j++) {//遍历找出最长上升序列
		if (ans < dp[j])
			ans = dp[j], pos = j;
	}
	while (pos != -1) {//链式访问
		cout << arr[pos] << " ";
		pos = path[pos];
	}
	cout << endl;
	cout << ans;
}

注：该代码为逆序输出最长子序列，想要正序可以采用记忆化搜索，或者用临时数组正向输出。

可以看到，dp思路遍历了两层循环寻找最值，如果能优化内层循环为logn，整个效率就上来了。

这里我们采用贪心+二分的思路

首先， 这里的贪心思路是：对于一个上升子序列。

如果他最后一个元素越小，那么他越有可能接上其他元素。

由此，在以每一个元素为起点遍历的时候，我们在挑选尾元素时，在每个相同的子序列位置上，我们可以挑选最小的那个值。

这里我要解释一下什么叫 每个相同的子序列位置上

由这个思路，并不是直接去寻找原序列中最小的元素然后接在子序列上，而是如果在原序列中子序列当前的元素之后存在一个小于子序列最尾元素的值，首先因为他比尾元素小，我们不会将他推入子序列，不然就破坏了子序列的上升性。

但是我们可以用它把子序列里第一个大于等于他的元素替换，也就是让这个子序列中的子序列的尾元素变小了，但是相对位置是没有改变的。

所以这个子序列更有可能变成最长上升子序列。

举个例子

对于一个序列：1，5，6，2，3，4

对于这个上升子序列 1，5，6 当匹配到 2 时，因为他小于子序列尾元素，所以不能推入子序列，但是对于这个子序列的先前状态 1，5，我们可以将第一个大于等于2的元素 5 替换为 2，因为这一替换就能使得1，2这个序列比1，5这个序列在之后的匹配下更有可能成为最长上升子序列。

实际上也确实是这样，观察这个序列。

很明显最长的序列是 1 ，2，3，4而不是1，5，6.

现在知道了如果当前原序列元素k小于子序列尾元素后，我们只需要找到第一个大于等于当前元素k的子序列元素，将其替换，即可。

这里又有一个细节，为什么不d出原序列第一个大于等于k的之后的元素，这样不就能直接得到最长上升子序列了吗？因为，你的替换 *** 作，只是让多个子序列同时进行匹配然后增长，这个匹配序列的长度为所有子序列的长度的最大值，如果有个子序列不断推入替换新元素，最后把原来比较大的那个子序列全替换了，则这个子序列成为最长上升子序列，他的长度即为匹配序列的长度。

但是这样做的缺点就是我们只能得到长度，而最长的子序列被破坏了。

注意：

注意题目的要求为严格递增的子序列，也就是不能存在相等的情况。

所以我们不能寻找第一个大于k的元素，因为这样替换完可能会出现k重复的情况。

所以我们要寻找第一个大于等于的元素，如果这个元素刚好与k相等，替换完不会出现重复的k。

知道了大致思路后，我们可以用二分查找优化寻找子序列中第一个大于等于k的元素使时间复杂度降为O(nlogn)

#include 
#include 
#include
#include
#include
using namespace std;
dequeq;
int myfind(int n) {//上升序列中查找第一个大于等于n的
	int l = -1, r = q.size();
	int mid = (l + r) >> 1;
	while (l + 1 != r) {
		mid = (l + r) >> 1;
		if (n < q[mid]) {
			r = mid;
		}
		else {
			l = mid;
		}
	}
	return r;
}
int arr[1000001];
int n;
int main()
{
	ios::sync_with_stdio(false); cout.tie(NULL);
	cin >> n;
	cin >> arr[0];
	q.push_back(arr[0]);
	int sum = 1;//单个元素即有序
	for (int j = 1; j < n; j++) {
		cin >> arr[j];
		if (arr[j] > q.back()) {
			q.push_back(arr[j]);
		}
		else {
//int t = lower_bound(q.begin(), q.end(), arr[j]) - q.begin();
			int t = myfind(arr[j]);
			q[t] = arr[j];
		}
	}
	cout << q.size() << endl;
}

注：stl自带二分查找函数，代码中注释的部分与自己写的二分等效，具体用法参见

二分模板 和 边界问题 及 相关STL使用 的小结_Brokenrivers的博客-CSDN博客二分查找应该算是我最早接触的一个算法了，那时候我看的c语言资料里的循环就是拿二分举例的。

同时二分的思想也非常好理解，但我没想到的是，这个算法看似非常简单，但是光是想要逻辑清晰的用二分找出一个个限定范围的数确实这么困难（指因为调二分的边界问题调到心态爆炸orz）。

在系统的思考和查阅资料后我现在才有把握，快速且不会因为思考边界问题而出错的手写出下列问题。

对于一个序列{1，2，3，5，5，5，8，9}①找出第一个 >=5 的元素②找出最后一个 <5 的元素③找出第一个 >5https://blog.csdn.net/m0_60777643/article/details/123774828的STL用法部分

其实下降和上升子序列的思路是一样的，同时也能调用STL的reverse函数反转下降序列为上升。

但是有些细节还是值得学习的。

这题第一问其实就是求最长下降子序列，且降序并不严格，可以出现相等的情况，这种边界条件非常重要。

第二问涉及其他知识，且本质就是寻找最长上升子序列，不加以讨论

我们按照上升子序列的思路来思考，dp写法就很简单了，只需要改变判断符号即可。

但是二分优化则有些麻烦。

我们这样想，对于一个序列 3 ，2，1 ，4，5，要求最长的下降子序列，那么一个下降子序列他的尾元素越大，越有可能接上新元素，越有可能成为最长下降子序列。

仿照上升子序列，那么我们只需要判断当前原序列的元素k是否小于等于（这题可以取等）尾元素，如果小于等于尾元素，则推入该元素，反之，则在子序列中寻找最后一个小于 k的的元素，进行替换。

为什么要找最后一个小于k的元素？

对于这样一个下降子序列 5 4 3 1 此时 k = 2我们要产生最有可能成为最长下降子序列的子序列，那么他的尾元素要尽可能大，所以我们找到第一个大于 k的元素。

同时注意，原题目是看存在相同元素的，所以必须要大于k的元素，如果找小于等于k的元素，原来与k相等的子序列元素就会被覆盖替换。

#include
using namespace std;
int n;
vector arr;
deque q1, q2;
int dp[1000001];
int dp1[1000001];
int nx[1000001];
int k = 1, ans = 1;
int main() {
	ios::sync_with_stdio(false); cout.tie(NULL);
	while (cin >> n) {
		if (n == -1) {
			break;
		}
		arr.push_back(n);
	}
	int s1 = 1, s2 = 1;
	q1.push_back(arr[0]);//先推入一个元素方便判断
	q2.push_back(arr[0]);
	for (int j = 1; j < arr.size(); j++) {
		if (arr[j] <=q1.back()) {
			q1.push_back(arr[j]);
		}
		else {
			int t = upper_bound(q1.begin(), q1.end(), arr[j], greater())-q1.begin();//找最后一个小于k的,倒序且不能取等
			q1[t] = arr[j];
		}
	}
	cout <

#include 
#include
#include
#include
using namespace std;
int n, m;
vectora1(100001), a2(100001);
dequeq;
int dp[10001][10001];
int main()
{
	cin >> n >> m;
	for (int j = 1; j <= n; j++) {
		char t;
		cin >> t;
		a1[j] = t - 'a' + 1;
	}
	for (int j = 1; j <= m; j++) {
		char t;
		cin >> t;
		a2[j] = t - 'a' + 1;
	}
	for (int j = 1; j <= n; j++) {
		for (int i = 1; i <= m; i++) {
			dp[j][i] = max(dp[j - 1][i], dp[j][i - 1]);
			if (a1[j] == a2[i]) {
				dp[j][i] = max(dp[j][i], dp[j - 1][i - 1] + 1);
			}
		}
	}
	cout << dp[n][m];
}