自动搬运

查看原文

来自洛谷，原作者为

	beicige 6

搬运于2025-08-24 23:13:16，当前版本为作者最后更新于2025-07-18 10:06:08，作者可能在搬运后再次修改，您可在原文处查看最新版

自动搬运只会搬运当前题目点赞数最高的题解，您可前往洛谷题解查看更多

以下是正文

题意

给出一个长度为 n 的正整数数组 $a_1, a_2, \dots , a_n$ 。可以对任意一个区间进行翻转。然后找出连续相同数字区间长度与相同数字之积的最大值。

思路

很明显题目要求把两段所有数都相同的区间合并。所以我们可以求出每一个数字连续出现次数的最大值和次大值。对于每一个数字，这样两个区间通过翻转合并后的长度一定为最长。

然后枚举所有数字可获得的分数，求出得分最大值即可。

代码

#include<bits/stdc++.h>
using namespace std;
long long n,a[1000010],m[1000010][3],cnt,ans,ma=-1,mi=INT_MAX;
//m数组存储每一个数字的最大和次大长度，ma和mi存储数字的最大值和最小值 
//cnt存储当前长度 
int main(){
	ios::sync_with_stdio(0),cin.tie(0),cout.tie(0); 
	cin>>n; 
	for(int i=1;i<=n;i++){
		cin>>a[i];
		ma=max(ma,a[i]),mi=min(mi,a[i]);//记录最大值和最小值 
	}
	for(int i=1;i<=n;i++){
		cnt++;//当前长度增加 
		if(a[i]!=a[i+1]||i==n){//如果下一位数字与当前数字不相同 
			if(cnt>m[a[i]][1]) m[a[i]][2]=m[a[i]][1],m[a[i]][1]=cnt;//是目前最长，则把原本最长下调至第二长 
			else if(cnt>m[a[i]][2]) m[a[i]][2]=cnt; //修改为第二长 
			cnt=0;//注意计数器清零 
		}
	}
	for(int i=mi;i<=ma;i++){//从所有数字的最小值到最大值 
		ans=max(ans,(m[i][1]+m[i][2])*i);//ans存储答案。最长与次长之和是翻转后的长度，与当前数字相乘得到分数 
	}
	cout<<ans;
}