本文共 1167 字，大约阅读时间需要 3 分钟。

感觉太巧妙了吧…怎么也想不到

开始一直以为是树状数组什么的…没想到是思维题

$用dp[x]数组维护删除后对整个序列的record数量$

$设当前第i个数字是a_i,假如a_i既不是最大也不是次大那么压根不用管$

$因为删掉前面的任意一个数不可能使a_i变成record$

$删掉a_i不会使后面的数字成为record$

$那么当a_i是[1,i]最大的,删掉a_i使序列record减去1,dp[a_i]--$

$当a_i是次大的,删掉[1,i]的最大值使a_i成为record,dp[max]++$

#include 
   
    using namespace std;const int maxn=3e5+10;int dp[maxn],n,x,max1,max2;int main(){	cin>>n;	for(int i=1;i<=n;i++)	{		cin >> x;		//x是当前最大值,若去掉x对[1,i]的贡献是-1 		if(x>max1)	dp[x]--,max2=max1,max1=x;		//x是次大值,那么去掉[1,i]的最大值可以让x变成最大值 		else if(x>max2)	dp[max1]++,max2=x;	}	int ans=1;	for(int i=1;i<=n;i++)		if(dp[i]>dp[ans])	ans=i;	cout<
   

转载地址：https://issue-is-vegetable.blog.csdn.net/article/details/107102971 如侵犯您的版权，请留言回复原文章的地址，我们会给您删除此文章，给您带来不便请您谅解！