Backtracking Solution (TLE of course). In case you are curious.
Typical DP/DC problem, but providing one possible backtracking solution just in case you are curious. TLE. \n\n\npublic class Solution {\n    boolean[] used; \n
Typical DP/DC problem, but providing one possible backtracking solution just in case you are curious. TLE. \n\n```\npublic class Solution {\n    boolean[] used; \n    int[] nums; \n    public int maxCoins(int[] nums) {\n        this.used = new boolean[nums.length];\n        this.nums = nums; \n        int max = 0; \n        for(int i = 0; i<nums.length; i++){\n            used[i] = true;  \n            max = Math.max(helper(i), max);\n            used[i] = false; \n        }\n        return max;\n    }\n    private int helper(int cur){\n        int left = cur-1, right = cur+1; \n        while(left>=0 && used[left]) left--; \n        left = (left == -1) ? 1 : nums[left]; \n        while(right<nums.length && used[right]) right++; \n        right = (right == nums.length) ? 1 : nums[right]; \n        \n        int max = 0; \n        for(int i = 0; i<nums.length; i++){\n            if(used[i]) continue; \n            used[i] = true; \n            max = Math.max(helper(i), max); \n            used[i] = false; \n        }\n        \n        return nums[cur] * left * right + max; \n    }\n}\n```
[]