#include <bits/stdc++.h>
using namespace std;
const int N=300005;
int a[N],n;
int vis1[N],vis2[N];
int main()
{
	int x=0,y=0;
	cin>>n;
	for(int i=1;i<=n;i++)
	cin>>a[i];
	int ans=-1;
	vis1[a[1]]++;
	x++;
	for(int i=2;i<=n;i++) 
	{
		if(!vis2[a[i]]) y++;
		vis2[a[i]]++;
	}
	ans=max(ans,x+y);
	for(int i=2;i<n;i++) //1-i -- i+1-n 
	{
		vis2[a[i]]--;
		vis1[a[i]]++;
		if(!vis2[a[i]]) y--;
		if(vis1[a[i]]==1) x++;
		ans=max(ans,x+y);
	}
	cout<<ans;
}

题目大意

给你一个长度为 N 的整数序列： $A=(A_1,A_2,…,A_ N​)。$

当把一个位置上的 A 分割成两个非空（连续）子数组时，求这两个子数组中不同整数个数之和的最大值。

更具体地说，求整数 $i$ 在 $1\le i\le N−1$ 中的以下两个值的最大和：$A=(A_1,A_2,…,A_ i)。$ 中的不同整数计数，以及 $A=(A_{i+1},A_{i+2},…,A_N)$ 中的不同整数计数。

题目思路

如果直接枚举分割点，那么肯定爆炸，所以考虑其他方法。 开两个数组，一个从前往后搜，一个从后往前搜，再来一个标记数组看这个数重复没有，最后求两个数组相对应的数的和的最大值就行了。 就相当于是暴力，但暴力是分成了两段是双层循环，这个也是分两段，只有一层循环。

#include<bits/stdc++.h>
using namespace std;
const int N=3e5+6;
int n,ans,a[N],x[N],y[N];
bool k[N];//标记数组 
int main(){
	cin>>n;
	for(int i=1;i<=n;i++) cin>>a[i];
	for(int i=1;i<=n;i++){
		x[i]=x[i-1];//求不同数的个数 
		if(k[a[i]]==0) x[i]++,k[a[i]]=1;//是第一次标记没重复 
	}
	for(int i=1;i<=n;i++) k[i]=0;//清空 
	for(int i=n;i>=1;i--){
		y[i]=y[i+1];//倒着求 
		if(k[a[i]]==0) y[i]++,k[a[i]]=1;//标记 
	}
	for(int i=1;i<n;i++) ans=max(yly,x[i]+y[i+1]);//求每个搭配的最大值 
    return 0;
}