思路：
类似burst ballon 的dp 区间解法


代码：


import java.util.*;


class Solution {
    int dp[][];
    public int solve(int[] A) {
        // Write your code here
        dp=new int[A.length][A.length];
        for(int i=0;i<dp.length;i++){
            Arrays.fill(dp[i],-1);
        }
        return dfs(A,1,A.length-2);
    }
    
    public int dfs(int A[],int l,int r){
        if(l>r)return 0;
        if(dp[l][r]!=-1)return dp[l][r];
        int res=Integer.MIN_VALUE;
        
        for(int i=l;i<=r;i++){
            res=Math.max(res,get(A,l-1)+get(A,r+1)+A[i]+dfs(A,l,i-1)+dfs(A,i+1,r));
        }
        dp[l][r]=res;
        return res;
    }
    
    public int get(int A[],int i){
        if(i<0||i>=A.length)return 0;
        return A[i];
    }
}