最长上升子序列

定义：给出一个数字序列（arr），求出其中长度最长的数值严格递增的子序列

做法一：使用动态规划，我们定义dp[i]为以arr[i]结尾的最长上升子序列的长度。

#include<bits/stdc++.h>
using namespace std;
int main()
{ios::sync_with_stdio(0);cin.tie(0);cout.tie(0);int n;cin>>n;vector<int> v(n+1,0);for(int i=1; i<=n; i++) cin>>v[i];vector<int> dp(n+1);dp[1] = 1;int res=1;for(int i=2; i<=n; i++){int maxn = 0;for(int j=1; j<i; j++){if(v[j]<v[i]) maxn = max(maxn,dp[j]);}dp[i] = maxn+1;res = max(res,dp[i]);	}cout<<res<<endl;return 0;
}

做法二：我们如果仅仅需要求出最后的结果，可以考虑贪心＋二分查找来优化。

我们对于遍历到的每一个元素，我们都在dp数组中去寻找第一个大于等于它的元素，如果没有，代表它最大，所以直接加入dp，如果找到，则更新这个位置为当前元素，以此来保证为未来提供更小的末尾序列。

#include<bits/stdc++.h>
using namespace std;
int main()
{ios::sync_with_stdio(0);cin.tie(0);cout.tie(0);int n;cin>>n;vector<int> v(n+1,0);for(int i=1; i<=n; i++) cin>>v[i];vector<int> dp;for(int i=1; i<=n; i++){int now = v[i];auto x = lower_bound(dp.begin(),dp.end(),now);if(x==dp.end()) dp.push_back(now);else *x = now;}cout<<dp.size()<<endl;return 0;
}

最长公共子序列

定义：给出两个数字序列，求出两个数字序列的最长子序列的长度。

若两个序列（记为arr1，arr2）中的数字是可以重复的，即最普遍的情况：

直接采用动态规划做法，我们定义dp[i][j]为arr1的前i个数和arr2的前j个数的最长子序列的长度。

我们对两个数组均进行从头遍历，若arr1[i]==arr2[i]，那么dp[i][j]可以直接由dp[i-1][j-1]加一得出。若不等，则为max（dp[i-1][j],dp[i][j-1]）。

#include<bits/stdc++.h>
using namespace std;
int main()
{int n;cin>>n;vector<int> v1(n+1,0);vector<int> v2(n+1,0);for(int i=1; i<=n; i++) cin>>v1[i];for(int i=1; i<=n; i++) cin>>v2[i];vector<vector<int>> dp(n+1,vector<int>(n+1,0));for(int i=1; i<=n; i++){for(int j=1; j<=n; j++){if(v1[i]==v2[j]) dp[i][j] = dp[i-1][j-1]+1;else dp[i][j] = max(dp[i-1][j],dp[i][j-1]);}}	cout<<dp[n][n]<<endl;return 0;
}

我们发现，当前状态只与上一个阶段的状态以及当前状态的j-1有关，所以我们可以去掉第一个维度

#include<bits/stdc++.h>
using namespace std;
int main()
{int n;cin>>n;vector<int> v1(n+1,0);vector<int> v2(n+1,0);for(int i=1; i<=n; i++) cin>>v1[i];for(int i=1; i<=n; i++) cin>>v2[i];vector<int> dp(n+1,0);for(int i=1; i<=n; i++){for(int j=1; j<=n; j++){if(v1[i]==v2[j]) dp[j] = dp[j-1]+1;else dp[j] = max(dp[j],dp[j-1]);}}cout<<dp[n]<<endl;return 0;
}

这样做的时间复杂度是O(n²)的

若两个序列（记为arr1，arr2）是排列，即元素不重复【洛谷：P1439 【模板】最长公共子序列】：

我们可以将问题转换为LIS来做。

我们将arr1中的元素值和位置做一个映射，然后将arr2中的元素全部转换为位置。

理由：因为公共子序列要求两个序列中顺序相同，而如果arr1和arr2具有公共子序列，那么他们的索引一定都是递增的，所以最长递增子序列此时就是最长公共子序列。

#include<bits/stdc++.h>
using namespace std;
int main()
{int n;cin>>n;vector<int> v1(n+1,0);vector<int> v2(n+1,0);vector<int> pos(n+1,0);vector<int> arr(n+1,0);for(int i=1; i<=n; i++){cin>>v1[i];pos[v1[i]]=i;}for(int i=1; i<=n; i++){cin>>v2[i];arr[i] = pos[v2[i]];	}vector<int> dp;for(int i=1; i<=n; i++){int now = arr[i];auto x = lower_bound(dp.begin(),dp.end(),now);if(x==dp.end()) dp.push_back(now);else *x = now;}cout<<dp.size()<<endl;return 0;
}

这样的复杂度是O（nlogn）