这段代码的逻辑和前面的代码非常相似，但实现更加简洁，使用了 map 容器来记录每个元素的前驱索引。让我详细解释一下代码的结构和功能：

代码解析

1. 全局数组定义：

   const int N = 2e5 + 10;
   int a[N], p[N];
   

   • a[N]: 存储输入的数列。
   • p[N]: 这里的 p 数组已经不使用了，因为后续代码中使用了 map<int, int>，因此可以忽略此定义。

2. 输入处理：

   int n;
   cin >> n;
   for (int i = 1; i <= n; i++) {
       cin >> a[i];
   }
   

   • 读取输入的 n，表示有多少个元素。
   • 然后将输入的数列存入数组 a 中。

3. 初始化变量：

   int last = 0;
   int ans = 0;
   map<int, int> p;
   

   • last 用于记录最近一个和当前元素相同的元素的位置。
   • ans 用于保存答案，即最大不重复子序列的长度。
   • map<int, int> p：使用 map 代替数组 p，用于记录每个元素上次出现的位置。这里的 p[a[i]] 表示元素 a[i] 的上一次出现的位置。

4. 遍历并计算答案：

   for (int i = 1; i <= n; i++) {
       last = max(last, p[a[i]]);  // 更新最近出现相同元素的位置
       ans = max(ans, i - last);   // 计算当前不重复子序列的长度
       p[a[i]] = i;               // 更新当前元素出现的位置
   }
   

   • 遍历数组 a。
   • 对于每个元素 a[i]，首先通过 p[a[i]] 查找该元素上一次出现的位置，并更新 last，表示当前子序列中的最近一个重复元素的位置。
   • 然后计算当前子序列的长度，即 i - last，并更新 ans，取其最大值。
   • 最后更新 p[a[i]] = i，表示当前元素 a[i] 在第 i 个位置。

5. 输出答案：

   cout << ans;
   

   • 最后输出最大不重复子序列的长度 ans。

代码的实际含义

这段代码的目的是在一个数列中寻找最长的不含重复元素的子序列。通过记录每个元素上一次出现的位置，当遍历到一个重复元素时，计算从上一次重复元素的位置到当前的位置的子序列长度，并更新最长的子序列长度。

时间复杂度

• 遍历数组的时间复杂度是 $O(n)$。
• map 的插入和查找操作在均摊情况下为 $O(\log n)$，因此总体时间复杂度为 $O(n \log n)$。

示例

输入：

6
1 2 3 2 1 4

过程：

• a[1] = 1，last = 0，当前子序列长度为 1 - 0 = 1。
• a[2] = 2，last = 0，当前子序列长度为 2 - 0 = 2。
• a[3] = 3，last = 0，当前子序列长度为 3 - 0 = 3。
• a[4] = 2，last = 2（2 上一次出现在第 2 位），当前子序列长度为 4 - 2 = 2。
• a[5] = 1，last = 1（1 上一次出现在第 1 位），当前子序列长度为 5 - 1 = 4。
• a[6] = 4，last = 1，当前子序列长度为 6 - 1 = 5。

输出：

4

最长的不重复子序列是从位置 2 到 5，即 2 3 2 1 或 3 2 1 4。