我的思维漏洞

我找了好久的题解啊，最后只好对着别人提交的代码改错。。 我起初自认为找到了最优解的数学表达，即：

当我选择其中一点为起点后，只要我比较左右位置的a[i]大小，每次总优先跳到小的格子上，让大的格子尽量延后。这样我就可以得到当前起点下的最优解

如此，我只要枚举起点就好了。。

事实证明我错了，我花了好长时间来找反例。虽然标签说明了是区间DP，但我就是想尝试一下（呜呜~）

下面是正确的代码。

以二维数组下标作为左右区间端点，区间长度从1到n依次填表。大家都明白，不说了·

#include<iostream>
using namespace std;
int a[4100];
int dp[4100][4100]; 
//环形，无脑开两倍数组（其实也可以不开，就是处理时麻烦一点点）

int main()
{
    int n;
    cin >> n;
    for (int i = 1; i <= n; ++i)
    {
        cin >> a[i];
        dp[i][i]=a[i];
    }
    for(int i=n+1;i<=n+n;++i)
    {
         a[i]=a[i-n];
    }
    for(int len=1;len<=n;++len)//枚举区间长度
    {
         //枚举左端点
       //for(int i=1;i<=2*n-len+1;++i)    //法1：直接将n~2n的表也填上，这样就不用考虑那么多啦
         for(int i=1;i<=n;++i)                 //法2：将循环改为拷贝，本质还是和法1一样，填表
        {
           int j=i+len-1;
           dp[i][j]=max(dp[i+1][j]+len*a[i],dp[i][j-1]+len*a[j]);
           if(i>=1&&j<=n)
             dp[i+n][j+n]=dp[i][j];   
        }
    }
    //找最大区间
  int maxn=0;
  for(int i=1;i<=n;++i)
  {
      maxn=max(maxn,dp[i][i+n-1]);
  }
    cout<<maxn;
}