本文章由 WyOJ Shojo 从洛谷专栏拉取，原发布时间为 2022-03-22 09:31:13

题目大意

给出一个序列，可以将一个字段翻转，求最大相邻两个数的和。

思路

根据题目模拟翻转字段的左端点和右端点即可，我们注意到翻转后只会变两个数，也就是左右端点。于是，代码出来了。

#include <iostream>
#include <cstdio>
#include <algorithm> 
using namespace std;
int t,n,a[1005],maxn;
int main(){
	scanf("%d",&t);
	while(t--){
		maxn=0;
		scanf("%d",&n);
		for(register int i=1;i<=n;++i){
			scanf("%d",&a[i]);
			maxn=max(maxn,a[i]+a[i-1]);
		}
		for(register int i=1;i<n;++i){
			for(register int j=i+1;j<=n;++j){
				maxn=max(maxn,max(a[i-1]+a[j],a[i]+a[j]));
			}
		}		
		printf("%d\n",maxn);
	}
    return 0;
}

这就A了，但是我们可以继续优化。

考虑任何一组数列，都可以把最大数和第2大数挨在一起。因为我们可以翻转最大数右边的数到第2大数这个数列，使得最大数和第2大数挨在一起。

#include <iostream>
#include <cstdio> 
using namespace std;
int t,n,a[1005],maxn1,maxn2;
int main()
{
	scanf("%d",&t);
	while(t--){
		maxn1=maxn2=0;
		scanf("%d",&n);
		for(int i=1;i<=n;++i){
			scanf("%d",&a[i]);
			if(a[i]>maxn1)maxn2=maxn1,maxn1=a[i];\/\/如果有比最大还大的数，就先把最大的赋给第2大的，然后最大的再赋值
			else if(a[i]>maxn2)maxn2=a[i];
		}
		printf("%d\n",maxn1+maxn2);
	}
	return 0;
}