3.22阿里笔试第二题，测试能过，提交0%

import java.util.Scanner;

public class Main {
    //动态规划，返回以[i,j]段玩游戏所得到的最大值（j是包括在内的）
    public static int max(int i,int j,int[] sum,int[][] dp){
        if(dp[i][j]!=-1){
            return dp[i][j];
        }
        //如果只有两个数，则返回其中较小的那个数
        else if((i+1)==j){
            dp[i][j] = Math.min(sum[i+1]-sum[i],sum[j+1]-sum[j]);
            return dp[i][j];
        }

        else{
            int res = 0;
            //遍历切分点（切分点为右边第一个数坐标）
            for(int pos=i+1;pos<=j;pos++){
                //分别求左边和右边的数字和
                int l = sum[pos]-sum[i],r=sum[j+1]-sum[pos];
                //如果右边数字和小，则获得右边的分数并用右边继续游戏
                if(l>r){
                    res = Math.max(res,r+max(pos,j,sum,dp));
                }
                //如果左边数字和小，则获得左边的分数并用左边继续游戏
                else if(l<r){
                    res = Math.max(res,l+max(i,pos-1,sum,dp));
                }
                //如果两边一样大，则分别玩游戏取最大值
                else{
                    res = Math.max(res,Math.max(l+max(i,pos-1,sum,dp),r+max(pos,j,sum,dp)));
                }
            }
            dp[i][j] = res;
            return res;
        }
    }
    public static void main(String[] args) {
        Scanner in = new Scanner(System.in);
        while (in.hasNext()) {
            int n = in.nextInt();
            int[] values = new int[n];
            for (int i = 0; i < n; i++) {
                values[i] = in.nextInt();
            }
            int[][] dp = new int[n+1][n+1];
            for(int i=0;i<n;i++){
                for(int j=0;j<n;j++){
                    dp[i][j]=-1;
                }
            }
            //只剩一个数字的时候游戏结束
            for(int i=0;i<n;i++){
                dp[i][i] = 0;
            }
            int[] sum = new int[n+1];
            //前缀和数组，[i,j]段的和为sum[j+1]-sum[i]
            for(int i=1;i<=n;i++){
                sum[i] = sum[i-1]+values[i-1];
            }

            int res =  max(0,n-1,sum,dp);
            System.out.println(res);
        }
    }
}