C++ :

#include <bits/stdc++.h>
using namespace std;
const int N = 810,INF = 0x3f3f3f3f;
int n;
int a[N];//每堆石子的重量
int s[N];//前缀和
int mi[N][N];//mi[l][r]表示合并l,r区间的石子的最小代价
int ma[N][N];//ma[l][r]表示合并l,r区间的石子的最大代价

int main() {
	memset(mi,INF,sizeof(mi));
	memset(ma,-INF,sizeof(ma));
	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++){
		s[i] = s[i-1] + a[i];//前缀和
		mi[i][i] = 0;//边界 
		ma[i][i] = 0; 
	} 
	
	//状态计算：穷举区间长度
	for(int len = 2;len <= n;len++){
		//阶段：穷举区间的起点 
		for(int l = 1;l + len - 1 <= 2 * n;l++){
			//区间的终点
			int r = l + len - 1;
			//决策：穷举分割点
			for(int k = l;k < r;k++){
				mi[l][r] = min(mi[l][r],mi[l][k]+mi[k+1][r]+s[r]-s[l-1]);
				ma[l][r] = max(ma[l][r],ma[l][k]+ma[k+1][r]+s[r]-s[l-1]);
			} 
		}
	}
	
	//求长度为n的区间合并的最小值和最大值
	int minr = INF,maxr = -INF;
	for(int i = 1;i <= n;i++){
		minr = min(minr,mi[i][i+n-1]);//mi[1,n] mi[2,n+1] ... mi[n,2*n-1];
		maxr = max(maxr,ma[i][i+n-1]);//ma[1,n] ma[2,n+1] ... ma[n,2*n-1]
	} 
	
	cout<<minr<<endl<<maxr;
	return 0;
}