子序列子数组问题

分类

LCS(最长公共子序列)

LIS（最长上升子序列）

https://www.luogu.com.cn/problem/P1020#submit

如果直接写O(n平方)复杂度是很简单的,LIS递推方程如下

//dp[i]定义为以v[i]结尾的最长LIS
for(int i = 0; i < n; i++){
    for(int j = 0; j < i; j++){
        if(v[i] > v[j]){
            dp[i] = max(dp[i], dp[j] + 1)
        }
    }
}

LCS和LIS解决比较类似,但LCS不能用二分来优化,类似LCS问题的还有编辑距离

下面的是二分法的优化

#include <bits/stdc++.h>
using namespace std;
const int N = 2e5 + 5;
int a[N];
int g[N];//定义为长度为i的序列的最小/大末尾 
int n,cnt;

int main() {
	ios::sync_with_stdio(0);
	cin.tie(0),cout.tie(0);
	g[0] = INT_MAX;//非递增 
    while (cin>>a[++n]); 
    n -= 1; //超级重要,哥们因为这个点debug了好几次!!!!!!!! 
    for(int i = 1; i <= n; i++) {
		if(a[i] <= g[cnt]){
			g[++cnt] = a[i];
		}
		else{
			int l = 1, r = cnt-1;
			while(l <= r){
				int mid = (l + r)/2;
				if(g[mid] >= a[i]){
					l = mid + 1;
				}else{
					r = mid - 1;
				}
			}
			g[l] = a[i];
		}
	}
    cout << cnt << endl;
    
    cnt = 0; 
    memset(g, 0, sizeof(g));
    g[0] = INT_MIN;//递增 
     for(int i = 1; i <= n; i++){ 
		if(a[i] > g[cnt]){
			g[++cnt] = a[i];
		}
		else{
			int l = 1, r = cnt-1;
			while(l <= r){
				int mid = (l + r)/2;
				if(g[mid] < a[i]){
					l = mid + 1;
				}else{
					r = mid - 1;
				}
			}
			g[l] = a[i];
		}
	}
    cout << cnt << endl;
}