题解CF1654A

[题解]CF1654A 题目大意

给定数列 a a a ，可以至多将 a a a 的一段翻转，求 *** 作后数列相邻的数之和最大

解题思路

题目的样例，其实给了我们暗示：对于每一个数列 a a a ，其实只需要输出它最大两个数之和就是答案。

那么我们怎么来证明呢？

我们设数列中最大的两个数分别是 a i a_i ai​ 和 a j a_j aj​ ，这里我们不关心 a i a_i ai​ 和 a j a_j aj​ 谁大，只需要满足 j > i j>i j>i 。

那么我们把 a i + 1 , a i + 2 , . . . , a j a_{i+1},a_{i+2},...,a_j ai+1​,ai+2​,...,aj​ 翻转，就将 a i a_i ai​ 和 a j a_j aj​ 放到相邻位置了。

这时候它们之和就是答案了！

代码实现

#include
using namespace std;
int t,n,maxn1,maxn2,ai;//maxn1,maxn2表示数列中第一，第二大的数

int main()
{
	scanf("%d",&t);
	while(t)
	{
		--t;
		maxn1=0,maxn2=0;
		scanf("%d",&n);
		for(int i=1;i<=n;++i)
		{
			scanf("%d",&ai);
			if(ai>maxn1)
			{
				maxn2=maxn1;
				maxn1=ai;
			}
			else if(ai>maxn2)
			{
				maxn2=ai;
			}
		}
		printf("%d\n",maxn1+maxn2);
	}
 }