C++(g++ 7.5.0) 解法, 执行用时: 296ms, 内存消耗: 8232K, 提交时间: 2022-09-19 22:11:15

#include <bits/stdc++.h>
using namespace std;

#define ll long long

const int N = 2000010;
int n, ans;
int a[N];
int q[N], l, r;

int main()
{
	cin >> n;
	for (int i = 1; i <= n; i++)
	{
		cin >> a[i];
		a[i + n] = a[i];
	}
	for (int i = 1; i <= n + n; i++)
	{
		while (l < r && i - q[l + 1] > (n >> 1))
			l++;
		ans = max (ans, a[i] + a[q[l + 1]] + i - q[l + 1]);
		while (l < r && a[i] - i >= a[q[r]] - q[r])
			r--;
		q[++r] = i;
	}
	cout << ans << endl;
	return 0;
}

C++14(g++5.4) 解法, 执行用时: 249ms, 内存消耗: 15844K, 提交时间: 2019-08-22 10:05:48

#include<bits/stdc++.h>
using namespace std;
#define MAX 1000005

int num[MAX<<1];
int q[MAX<<1];
int l,r;

int main(){
	int n;
	scanf("%d",&n);
	for(int i=1;i<=n;i++){
		scanf("%d",&num[i]);
	}
	for(int i=1;i<=n;i++){
		num[i+n]=num[i];
	}

	l=r=1;
	q[1]=1;
	int ans=0;
	for(int i=2;i<=2*n;i++){
		while(l<=r&&q[l]<i-n/2)l++;
		ans=max(ans,num[i]+num[q[l]]+i-q[l]);
		while(l<=r&&((num[q[r]]-q[r])<=(num[i]-i)))r--;
		q[++r]=i;
	}
	
	cout<<ans<<endl;
	return 0;
}

C++ 解法, 执行用时: 256ms, 内存消耗: 8176K, 提交时间: 2022-01-16 11:53:30

#include<bits/stdc++.h>
using namespace std;
int a[2000001],l=1,r=1,ans,q[2000001],n;
int main(){
    cin>>n;
    for(int i=1;i<=n;i++)cin>>a[i],a[n+i]=a[i];
    for(int i=1;i<=n*2;i++){
        while(l<=r&&q[l]<(i-n/2))l++;
        ans=max(ans,a[i]+i+a[q[l]]-q[l]);
        while(l<=r&&a[q[r]]-q[r]<=a[i]-i)r--;
        q[++r]=i;
    }
    cout<<ans;
    return 0;
}