题解

题目难度：中等

知识点：动态规划、数组

解题思路：首先一看这种根据选择来取最大最小值的题，就应该想到可以使用动态规划进行解题，将整个大问题划分为小问题进行解决。难点主要在考虑怎么将大问题划分为小问题。然后，因为整个可选项是组成"环"的数据形式，所以在选择过程中，使用求余的方式来进行数据采取。
整个解题步骤：
第一步：因为使用动态规划进行解题，所以可以构建一个二维数组来保存数据。
第二步：这一步是对问题进行一个划分，因为只能选择首尾，所以只存在两种选项，我们需要对这个"选择"进行描述。因为这边求的是一个差，所以可以直接用二维数组保存这个差值。
dp[j][(k+j)%n] = max(-1dp[(j+1)%n][(k+j)%n]+num[j], -1dp[j][(k+j-1)%n]+num[(k+j)%n])
第三步：直接对这个二维数组进行数据比较，取最大值即可。

#include<iostream>
#include<cstring>
using namespace std;
#define max(a,b) (a>b?a:b)
int main(){
    int n;
    cin >> n;
    int dp[n+1][n+1];
    int num[n];
    for(int i=0; i<n; ++i) 
        cin >> num[i];
    int result = 0;
    memset(dp,0, sizeof(dp));
    for(int k=0; k<n; k++)
        dp[k][k] = num[k];
    for(int k=1; k<n; k++) {
        for(int j=0; j<n; j++) {
            dp[j][(k+j)%n] = max(-1*dp[(j+1)%n][(k+j)%n]+num[j], -1*dp[j][(k+j-1)%n]+num[(k+j)%n]);
            }
        }
    for(int i=0; i<n; ++i)
        result = max(dp[i][(i+n-1)%n], result);
    cout << result << endl;
    return 0;
}