虽然我感觉代码可能有点问题，但是依然是过了，大佬看出错误的话麻烦告诉我，n^2也能水过，想了一下每个序列中的元素都不重复，那么也就是说a2中的每个元素，最多有一个a1中的元素与之相等，在我们O(n^2)的算法中，我们的更新公式是

	for (int i = 1; i <= n; i++) {
		for (int j = 1; j <= n; j++) {
			if (a1[i] == a2[j])dp[i][j] = dp[i - 1][j - 1] + 1;
			else dp[i][j] = max(dp[i - 1][j], dp[i][j - 1]);
		}
	}

怎样才能利用已知条件把算法改成O(n）的，100w的数据nlogn也会T掉吧，其实在第二个for循环中，我们只会遇到一次a1[i]==a2[j]（数据不重复），因此我们用unorderedmap存储a1中的元素出现的位置，将第二个for循环去掉，如果a2[i]在map中出现过，显然有一个相等元素，那么如果他出现的位置比a2[i-1]在 a1中出现的位置还晚（如果出现的早的话是不可以的，比如1 3 2和1 2 3，a2中的3出现在a1中的位置比2早，1 2 3不是一个公共子序列），那么最长公共字串就可以+1，否则继承到上个元素为止的最大值，类似于dp[i][j]=max(dp[i-1][j],dp[i][j-1])操作。

#define ll long long
#define inf 0x3f3f3f3f
#define MAX 1000005
#define vec vector<int>
#define P pair<int,int>

int main() {
	int n, a1[MAX], a2[MAX], t[MAX];
	while (cin >> n) {
		unordered_map<int, int> m; m[0] = 0;
		for (int i = 1; i <= n; i++)cin >> a1[i], m[a1[i]] = i;//O(n)
		//由于元素均不相同，因此和a2[i]相同的a1中的元素不超过...