这题相对于弱化版，只多了两个要点 1 环结构 2 最大值 最大值不难，dp转移方程是一样的，只需要把min改成max，初始值-1e9就可以；

## 关于环结构：

1 2 3 4 5 模拟环结构，把它复制一遍到原数组之后： 1 2 3 4 5 1 2 3 4 5 这样就可以从中取出 2 3 4 5 1 3 4 5 1 2 4 5 1 2 3 5 1 2 3 4 SO，我们只需要枚举起点就可以

using namespace std;
int f[305][305];
int d[305][305];
int a[305];
int sum[305];
int main()
{
	int n;
	cin>>n;
	for(int i=1;i<=n;i++)
	{
		cin>>a[i];a[i+n]=a[i];
		sum[i]=sum[i-1]+a[i];
	}
	for(int i=n+1;i<=2*n;i++) sum[i]=sum[i-1]+a[i];
	for(int i=0;i<=2*n;i++)
		for(int j=0;j<=2*n;j++)
			if(i!=j)
			{
				f[i][j]=1e9;
				d[i][j]=-1e9;
			}
				
	for(int p=1;p<=n;p++)
	{
		for(int l=1;l<=n;l++)
			for(int i=p;i<=p+n-l;i++)
			{
				int j=i+l-1;
				for(int k=i;k<j;k++)
				{
					f[i][j]=min(f[i][j],f[i][k]+f[k+1][j]-sum[i-1]+sum[j]);
					d[i][j]=max(d[i][j],d[i][k]+d[k+1][j]-sum[i-1]+sum[j]);
				}
			}
	}
	int ans1=1e9;
	int ans2=-1e9;
	for(int i=1;i<=n;i++)
	{//	cout<<i<<":  ";
		ans1=min(ans1,f[i][i+n-1]);//cout<<f[i][i+n-1]<<"  ";
		ans2=max(ans2,d[i][i+n-1]);//cout<<d[i][i+n-1]<<endl;
	}
	cout<<ans1<<endl<<ans2;
	return 0;
}
//1 2 3 4 1 2 3 4
//1 2 3 4 5 1 2 3 4 5