#include<bits/stdc++.h>
using namespace std;
int n;//披萨个数
int pizza[500];//n个披萨大小
long cache[500][500];
int check(int id)
{
if(id<0)
id=n-1;//若取走披萨第一块的左边,则循环相当于最后一块
if(id>=n)
{
id=0;//若取走披萨最后一块的右边,则相当于第一块
}
return id;
}
long recursive(int l,int r)
{
//馋嘴先拿
if(pizza[l]>pizza[r])//馋嘴取左边
{
l=check(l-1);//馋嘴取完左边,剩下缺口的披萨左边位置
}
else//馋嘴取右边
{
r=check(r+1);
}
//由于吃货拿左边或者拿右边,递归时候可能会有重复,故二维数组保存l,r。若不为0,则说明之前已经递归过了
//比如l=1,r=4,吃货第一次拿左边时候递归,l=2,r=4,第二次再拿右边l=2,r=3,等价于第一次先拿右边l=1,r=3,第二次再拿左边l=2,r=3。(递归会存在重复,所以缓存判断一下可跳过一些递归)
if(cache[l][r]>0)
{
return cache[l][r];
}
//吃货再拿
if(l==r)//说明只剩一块了,最后一块也是吃货拿,题目说有奇数块,函数最终执行结束条件
cache[l][r]=pizza[l];
else
{
//说明还剩多块披萨,吃货可能拿左边,也可能拿右边,两边递归,取最大的可能值。也可以理解为递归暴力所有结果取最大值,相当于递归树里找最大的值
cache[l][r]=max(recursive(check(l-1),r)+pizza[l],recursive(l,check(r+1))+pizza[r]);
}
return cache[l][r];
}
int main()
{
cin>>n;
for(int i=0;i<n;i++)
{
cin>>pizza[i];
}
long chihuo=0;//吃货得到最大披萨大小
for(int i=0;i<n;i++)
{
//i-1左缺口,i+1右缺口
chihuo=max(chihuo,recursive(check(i-1),check(i+1))+pizza[i]);//吃货第一次取左边后,第二次可能取左或右,因此会出现重复情况,所以可以使用缓存保存可能的递归情况
}
cout<<chihuo<<endl;
return 0;
}