搜狐编程题第二题AC

public static void main(String[] args) {
        Scanner in = new Scanner(System.in);
        int n = in.nextInt();
        int[] nums = new int[n];
        for(int i = 0 ; i < n ; i++){
            nums[i] = in.nextInt();
        }
        int min = helper1(nums,n);
        System.out.println(min);
    }
    public static int helper1(int[] nums,int n){
        int sum = 0;
        for(int num : nums){
            sum+=num;
        }
        int[][] dp = new int[n][n];
        for(int j = 0 ; j < n ; j++){
            dp[j][j] = nums[j];
            for(int i = j-1 ; i >= 0 ; i-- ){
                dp[i][j] = Math.max(dp[i+1][j], dp[i][j-1]);
                if(nums[j] == nums[i]){
                    dp[i][j] = Math.max(dp[i][j],dp[i+1][j-1]+nums[j]+nums[i]);
                }
            }
        }
        return 2*sum-dp[0][n-1];
    }