This is a textbook example question variation.CLRS 15.2
\n\n/*\nThis question is the variation of the textbook question 15.2 how to minimize the sum of mutiplication.\nWhich is a classic dp problem.\n\nhere is how to
\n```\n/*\nThis question is the variation of the textbook question 15.2 how to minimize the sum of mutiplication.\nWhich is a classic dp problem.\n\nhere is how to maxmize the sum of multiplication \n\nthe relation ship is :\ndp[i][j]= min{dp[i][k-1]+dp[k+1][j]+ nums[i-1]*nums[k]*nums[j+1]} \nwhere k is{i,i+1,,,,j} and if(i-1)<0 nums[i-1]=1,if(j+1>=nums.length)(nums[j+1]=1)\nwe try all the dp[i][j] length from 1 to nums.length;\nand return the dp[0][nums.length-1]\n\nthe key loop is\nfor(int len=0; len<nums.lenth; len++){\n    for(int start=0; start<=nums.length-len; start++)\n        end =start+len-1;\n        for(int k=start; k<=end; k++)\n        dp[start][end]= Math.min(dp[start][end], dp[start][k-1]+dp[k+1][end]+nums[start-1]*nums[k]*nums[end+1]);\n}\nso this is a n^3 algrithm\n*/\n\n\nclass Solution {\n    public int maxCoins(int[] nums) {\n    if (nums == null || nums.length == 0) return 0;\n    \n    int[][] dp = new int[nums.length][nums.length];\n    for (int len = 1; len <= nums.length; len++) {\n        for (int start = 0; start <= nums.length - len; start++) {\n            int end = start + len - 1;\n            for (int i = start; i <= end; i++) {\n                int pre= start-1<0? 1: nums[start-1];\n                int next= end+1>=nums.length? 1: nums[end+1];\n                int coins = nums[i] * pre * next;\n                coins += i != start ? dp[start][i - 1] : 0; // If not first one, we can add subrange on its left.\n                coins += i != end ? dp[i + 1][end] : 0; // If not last one, we can add subrange on its right\n                dp[start][end] = Math.max(dp[start][end], coins);\n            }\n        }\n    }\n    return dp[0][nums.length - 1];\n }\n}\n```
[]