82pts求调

#include<iostream>
#include<algorithm>
using namespace std;
long long n,a[1005],dp[1005][1005];
void luogu(){
	for(int i=1;i<=n;i++)
		dp[i][i]=a[i]*n;
}
/*
            1 5
           /   \
         1 4   2 5
        /   \ /   \
      1 3   2 4   3 5
     /   \ /   \ /   \
   1 2   2 3   3 4   4 5
  /   \ /   \ /   \ /   \
1 1   2 2   3 3   4 4   5 5
O(n^2)  tip:这里如果标箭头的话应该往下指，表示分解 
*/
int main(){
	ios::sync_with_stdio(0);
	cin.tie(0);
	cout.tie(0);
	
	cin>>n;
	for(long long i=1;i<=n;i++)cin>>a[i];
	luogu();
	for(long long len=2;len<=n;len++){
		for(long long s=1;s<=n+1-len;s++){
			long long e=s+len-1;
			dp[s][e]=max(dp[s][e-1]+a[e]*(n+1-len),dp[s+1][e]+a[s]*(n+1-len));
		}
	}
//	for(long long i=1;i<=n;i++){
//		for(long long j=1;j<=n;j++){
//			printf("%d ",dp[i][j]);
//		}
//		printf("\n");
//	}
	cout<<dp[1][n];
	
	return 0;
}