状态定义：
一眼区间$DP$，从左右两边删不好定义状态，不如定义$dp[i][j]$表示$[i,j]$未删的最大值，转移就很自然了
转移：
从左边删$dp[i][j]=max(dp[i][j],dp[k][j]+abs(a[i-1]-a[k])*(i-1-k+1))$
删除区间$[k,i),i-1>k$
从右边删$dp[i][j]=max(dp[i][j],dp[i][k]+abs(a[j+1]-a[k])*(k-j));$
删除区间$(j,k],k>j+1$
但是这样转移是转移不了只删一个的，特殊搞一下就好
$dp[i][j]=max(dp[i][j],dp[i-1][j]+a[i-1])$
$dp[i][j]=max(dp[i][j],dp[i][j+1]+a[j+1])$
答案统计：
$ans=max(ans,dp[i][j]+abs(a[j]-a[i])*(j-i+1))$
答案就是$DP$数组之中，删完的最小值
#include<iostream>
#include<cstdio>
#include<cmath>
using namespace std;
int n,a[],dp[][],ans;
int main()
{
scanf("%d",&n);
for(int i=;i<=n;i++)
scanf("%d",&a[i]);
for(int l=n-;l;l--)
for(int i=;i<=n-l+;i++)
{
int j=i+l-;
dp[i][j]=max(dp[i][j],dp[i-][j]+a[i-]);
dp[i][j]=max(dp[i][j],dp[i][j+]+a[j+]);
for(int k=;k<i-;k++)
dp[i][j]=max(dp[i][j],dp[k][j]+abs(a[i-]-a[k])*(i--k+));
for(int k=j+;k<=n;k++)
dp[i][j]=max(dp[i][j],dp[i][k]+abs(a[j+]-a[k])*(k-j));
ans=max(ans,dp[i][j]+abs(a[j]-a[i])*(j-i+));
}
printf("%d\n",ans);
return ;
}