试题分析

容易发现性质，选择的是一段区间，但是贪心无法去维护这件事情，所以考虑$dp$,且我们只要去设计关于$JOI$的选择。

设$dp(i,j)$为现在要在$[l,r]$区间内选择,然后就可以随便写了。

#include
      
       #include
       
        #include
        
         #include
         
          #define int long longusing namespace std;inline int read(){    int f=1,ans=0;char c=getchar();    while(c<'0'||c>'9'){
    if(c=='-')f=-1;c=getchar();}    while(c>='0'&&c<='9'){ans=ans*10+c-'0';c=getchar();}    return f*ans;}const int N=4001;int dp[N][N],n,val[N],maxn;int dfs(int l,int r){    if(l==r) return dp[l][r]=val[l];    if(l+1==r) return dp[l][r]=max(val[l],val[r]);    if(dp[l][r]!=-1) return dp[l][r];     int res=0;    if(val[l+1]>val[r]) res=max(res,dfs(l+2,r)+val[l]);    else res=max(res,dfs(l+1,r-1)+val[l]);    if(val[l]