为得到（1，n）整个区间上卖出方案所得到金钱的最大值，可以从区间（2，n）和（1，n-1）得到，同样的以此类推，最终可将方案归到最小长度的区间。我们找到了递归的出口。

——由小区间的最优值得到大区间的最优值，不就是区间DP所能解决的问题吗。

还记得我们上方的区间DP板子吗，O（n^3）的复杂度，内部有一层对断点K的遍历，然而本题已经说明取数只能从头或者尾部选择，这就少了对K的遍历。

根据题义某一区间的最优值来自于len-1的子区间，我们可以写出状态转移方程。

//区间DP 
#include<iostream>
#include<cstdio>
#include<cmath>
#include<cstring>
#include<algorithm>
#include<limits.h>
#include<iomanip>
using namespace std;
 
int n,v[2005];
int dp[2005][2005];
//dp[i][j]表示从区间i到j所能得到的局部最优消费值 
 
int main(){
	ios::sync_with_stdio(0);
	cin.tie(0);
	cin>>n;
	for(int i=1;i<=n;++i){
		cin>>v[i];
		dp[i][i]=v[i]*n;//初始化dp 
	} 
	//区间dp板子
	for(int len=2;len<=n;++len){
		for(int left=1;left<=n;++left){//i为区间左端点 
			int right=left+len-1;
			if(right>n)continue;
			dp[left][right]=max(dp[left+1][right]+v[left]*(n-len+1),dp[left][right-1]+v[right]*(n-len+1));
		}
	} 	
	cout<<dp[1][n];
	return 0;
}