糖果游戏

import java.util.*;

// 环：复制一倍结尾, 枚举分割点, 取max
// DP[i][j]表示candy[i~j]中先手比后手多拿的糖果数
// 区间DP

public class Main {
    public static void main(String[] args) {
        Scanner in = new Scanner(System.in);
        int n = in.nextInt();
        int[] candy = new int[n << 1];
        for (int i = 0; i < n; i++) {
            candy[i] = candy[i + n] = in.nextInt();
        }

        memo = new int[n << 1][n << 1];
        for (int[] row : memo) Arrays.fill(row, -1);
        int res = 0;
        for (int i = 0; i < n; i++) { // [i, i+n-1]
            res = Math.max(res, dfs(candy, i, i + n - 1)); // 最大
        }
        System.out.println(res);
    }

    static int[][] memo;
    static int dfs(int[] candy, int i, int j) {
        if (i == j) return candy[i];
        if (memo[i][j] != -1) return memo[i][j];
        return memo[i][j] = Math.max(candy[i] - dfs(candy, i + 1, j), candy[j] - dfs(candy, i, j - 1));
    }
}