求条P2858

#include <bits/stdc++.h>
using namespace std;
int n,dp[2005][2005],num[2005];
int main()
{
	cin >> n;
	for (int i = 1;i <= n;i++)
	{
		cin >> num[i];
		dp[i][i] = num[i] * n;
	}
	for (int len = 2;len <= n;len++)
	{
		for (int i = 1;i <= n;i++)
		{
			int j =  i + len - 1;
			int day = n - len + 1;
			dp[i][j] = max(dp[i - 1][j] + num[i] * day,dp[i][j - 1] + num[j] * day);
		}
	}
	cout << dp[1][n];
	return 0;
}