题解：AT_abc397_c [ABC397C] Variety Split Easy

· · 题解

题目大意：

有 n 个数，将这 n 个数分成两段连续的子序列，求这两个子序列中不同元素数量的最大值。

因为是求不同元素的数量，所以我们要去重。而众所周知， 有一个叫 set 的东西，能自动去重。但是，我们不能把整个数列一起塞进 set 里，因为两个子序列中可能分别有两个相同的数，要算入各自的答案里。于是，易想到开两个 set 。一个存左子序列的答案，一个存右子序列的答案。最后把 1 到 n 的左右答案加起来求 max 就可以了。

代码如下：

#include <bits/stdc++.h>

using namespace std;
int n;
int a[300010];
int l[300010], r[300010];
set<int> sl, sr;

int main(){
    int n;
    cin >> n;
    for (int i = 1; i <= n; i++)
        cin >> a[i];
    for (int i = 1; i <= n; i++){
        sl.insert(a[i]);
        l[i] = sl.size();
    }
    for (int i = n; i >= 1; i--){//注意要从大到小循环
        sr.insert(a[i]);
        r[i] = sr.size();
    }
    int ans = 0;
    for (int i = 1; i < n; i++){
        int sum = l[i] + r[i + 1];//左答案是1 -- i，右答案是i + 1 -- n
        ans = max(ans, sum);
    }
    cout << ans;
    return 0;
}