abc397c

zby0501_ · 2025-03-16 12:46:13 · 题解

思路：

本题其实还是挺套路的。

首先，因为题目要求我们把原数组分成两段，求两段数组不重复的数的和的最大值。看一下数据范围，n \le 3 \times 10^5，所以我们要用类似前缀和预处理的方式。

首先，从前往后预处理。当出现新元素时，就把预处理数组比之前加 1。否则直接复制前一个元素。从后往前同理。

算答案时，把两段和的最大值求一下就行了。

代码：

#include<bits/stdc++.h>
//#define int long long
using namespace std;
int s1[300005],s2[300005],n,a[300005];
map<int,bool>m1,m2;
signed main(){
    //freopen(".in","r",stdin);
    //freopen(".out","w",stdout);
    ios::sync_with_stdio(0);
    cin.tie(0),cout.tie(0);
    cin>>n;
    for(int i=1;i<=n;++i) cin>>a[i];
    for(int i=1;i<=n;++i){
        if(!m1[a[i]]){
            s1[i]+=s1[i-1]+1;
            m1[a[i]]=1;
        }
        else s1[i]+=s1[i-1];
    }
    for(int i=n;i>=1;--i){
        if(!m2[a[i]]){
            s2[i]+=s2[i+1]+1;
            m2[a[i]]=1;
        }
        else s2[i]+=s2[i+1];
    }
//  for(int i=1;i<=n;++i) cout<<s1[i]<<' '<<s2[i]<<'\n';
    int ans=0;
    for(int i=1;i<n;++i)
        ans=max(ans,s1[i]+s2[i+1]);
    cout<<ans;
    return 0;
}