8613 锁



在显示出这些数字后1分钟内，输入答案密码就可以解锁。解锁密码Key的计算方法如下：
在这个环内选两个数，这两个数之和再加上这两个数在环内最短距离就是一个伪Key。最大的伪Key就是真正的解锁密码Key。
例如图2，选择26和15，从26逆时针走4步到15。则伪Key是26+15+4=45


但图3中，选择26，33，从26顺时针走3步到33。得到的伪Key是26+33+3=62。而且没有其他的伪Key比62大。所以Key为62。

Oyy很满意这个设计。因为他觉得除了我们的acm队员外，其他人是不能在1分钟内求出Key并输入的。你想成为acm队的一员吗？那得先“入门”：）




输入格式

输入包括多个Case，每个Case包含两行。第一行包括一个正整数N。表示环内数的个数。第二行包括n个正整数。所有正整数小于5000。最后以N为0为结束。



输出格式

每个Case包含1行输出。就是解锁Key。



输入样例

2
1 2
12
13 28 33 5 6 19 21 15 12 19 8 26
0



输出样例

4
62

不知道怎么做  求指点

这个明显是暴力 严重超时
这里有个代码 水过去了
#include <iostream>
#include <stdio.h>
#include <utility>
#include <stdlib.h>
#include <string.h>
using namespace std;
int a[200000]= {0};
int Tr[200000]={0};
int main()
{
    int n;
    while(scanf("%d",&n)&&n)
    {
        memset(Tr,0,sizeof(Tr));
        for(int i=0; i<n; i++)
        {
            scanf("%d",&a[i]);
        }
        for(int i=n; i<3*n/2; i++)
        {
            a[i]=a[i-n];
        }
        int maxn=a[0],term;
        pair<int,int>s,d;
        s.first=a[0];
        s.second=0;
        for(int j=1; j<=3*n/2; j++)
        {
            if(j-s.second>n/2)
            {
                int ma=-0x7fffffff,bi=s.second+1;
                for(int y=s.second+1;y<j;y++)
                {
                    if(Tr[y]>ma)
                    {
                        ma=Tr[y];
                        bi=y;
                    }
                    else
                    {
                        Tr[y]=a[y]-y+bi;
                    }
                }
                s.first=a[bi];
                s.second=bi;
            }
            term=s.first+a[j]+j-s.second;
            if(maxn<term)
            {
                maxn=term;
            }
            if(a[j]-j+s.second>=s.first)
            {
                s.first=a[j];
                s.second=j;
            }
            else
            {
               Tr[j]=a[j]-j+s.second;
            }
            if(s.second>=n) break;
        }
        printf("%d\n",maxn);
    }
    return 0;
}
求标准解法

标准解法
单调队列  现在感觉好简单