然后发现，与 $y$ 有关的部分中只有 $i$ 和 $x$ 没有 $j$。于是用 $g_{i,x}$ 表示对于这对 $(i,x)$ 最好的 $y$ 产生的最大值，即：

这个东西中包含一个 $f_{x,y}$ 比较烦，考虑一边求 $f$ 一边更新 $g$。具体来说，枚举 $i,j$，在循环里要做这些事：

1. 枚举 $x$，通过 $g$ 快速计算 $f_{i,j}$ 的值；
2. 将 $(i,j)$ 当做 $g$ 中的 $(x,y)$，枚举 $g$ 中的 $i$，更新 $g$。

这段还是看程序比较好懂吧，可以先跳到下面程序部分搞懂再往下。

然后，还有一点细节要注意：$g$ 的式子里面 $y$ 其实是要大于“$j$”，但是不能把 $j$ 记下来（不然就爆炸了），要通过一些手段使得当前 $g$ 中存的都是大于 $j$ 的答案。于是外层枚举 $j$ 并倒序枚举。

还有一个小问题：$(i-1,j)$ 是不能转移到 $(i,j)$ 的，但是如果内层循环 $i$ 正序枚举，那么在 $f_{i-1,j}$ 时更新了 $g_{i,i-1},g_{i+1,i-1}\cdots$；在 $f_{i,j}$ 时需要的有 $g_{i,i-1},g_{i,i-2}$，其中 $g_{i,i-1}$ 重复了，于是内层的 $i$ 也要倒序循环。

时间复杂度 $\mathcal O(n^3)$，代码：

#include<bits/stdc++.h>
using namespace std;
long long a[305],f[305][305],g[305][305];
inline int read()
{
	char c=getchar();
	int x=0,y=1;
	while(c<'0'||c>'9')
	{
		if(c=='-')
			y=-1;
		c=getchar();
	}
	while(c>='0'&&c<='9')
	{
		x=(x<<3)+(x<<1)+c-'0';
		c=getchar();
	}
	return x*y;
}
int main()
{
	int n=read(),i,j,k;
	long long ans=-1000000000000000000ll;
	for(i=1;i<=n;i++)
		a[i]=read();
	for(i=1;i<=n;i++)
		for(j=1;j<=n;j++)
			g[i][j]=-1000000000000000000ll;
	for(j=n;j;j--)//外层枚举j并倒序枚举，上面有解释
		for(i=j-1;i;i--)//内层枚举i并倒序枚举，上面有解释
		{
			f[i][j]=a[i]*(n-j+1)-a[j]*i;//不转移的情况
			for(k=1;k<i;k++)//这里的k就是转移方程中的x
				f[i][j]=max(f[i][j],g[i][k]-a[i]*j+a[k]*j-a[j]*i+a[j]*k);
			ans=max(ans,f[i][j]+(a[j]-a[i])*(j-i));
			for(k=i+1;k<j;k++)//这里的k就是g[i][x]中的i
				g[k][i]=max(g[k][i],f[i][j]+a[k]*j-a[i]*j+a[j]*k-a[j]*i);
		}
	for(i=1;i<=n;i++)
		ans=max(ans,a[i]*(n-i+1)-a[i]*i);
	for(i=1;i<n;i++)
		for(j=i+1;j<=n;j++)
			for(k=i+1;k<j;k++)
				ans=max(ans,f[i][j]+(a[k]-a[i])*(j-k)+(a[j]-a[k])*(k-i));
	printf("%lld",ans);
	return 0;
}