#include<iostream> #include<cstring> #include<cstdio> using namespace std; long long n,a[4001],sum[4001]={0},f_max[4001][4001]={0}; void init(); void work(); int my_min(int,int); int my_max(int,int); int main() { //freopen("stone5.in","r",stdin); //freopen("stone5.out","w",stdout); init(); work(); return 0; } void init() { cin>>n; for(int i=1;i<=n;i++) { cin>>a[i]; a[i+n]=a[i]; } for(int i=1;i<=2*n;i++) sum[i]=sum[i-1]+a[i]; } void work() { for(int d=2;d<=n;d++) { for(int i=1;i<=2*n-d+1;i++) { int j=i+d-1; //f_min[i][j]=0x7fffffff/2; /*for(int k=i;k<j;k++) { f_max[i][j]=my_max(f_max[i][j],f_max[i][k]+f_max[k+1][j]); f_min[i][j]=my_min(f_min[i][j],f_min[i][k]+f_min[k+1][j]); }*/ f_max[i][j]=my_max(f_max[i+1][j],f_max[i][j-1])+sum[j]-sum[i-1]; //f_min[i][j]=my_min(f_min[i+1][j],f_min[i][j-1])+sum[j]-sum[i-1]; //cout<<d<<' '<<sum[j]-sum[i-1]<<' '<<i<<' '<<j<<' '<<f_min[i][j]<<endl; } } long long tot2=0; //for(int i=1;i<=n;i++) tot1=my_min(tot1,f_min[i][i+n-1]); for(int i=1;i<=n;i++) tot2=my_max(tot2,f_max[i][i+n-1]); cout<<tot2<<endl; } int my_min(int x,int y) { if(x<y)return x; else return y; } int my_max(int x,int y) { if(x>y)return x; else return y; } /************************************************************** Problem: 1685 User: zhanghanbin Language: C Result: Compile Error ****************************************************************/