Simple Java Solution Using MCM
Clearly this problem is very similar to classic Matrix Chain Multiplication Problem in DP. To generate the MCM type solution we need 3 things , first the base c
Clearly this problem is very similar to classic Matrix Chain Multiplication Problem in DP. To generate the MCM type solution we need 3 things , first the base condition - to think of the base condition we can take smallest invalid input for i & j which is i = j+1 or in general i>j, therefore return 0. Now we can think of recursively calculating the answer -> we start a loop from `i` till `j` which are the start and end index of the array(`0` and `arr.length`) .Now we will choose any index to be evaluated at last then the indices before and after the chosen index will be solved recursively in the same manner. At last we will calculate the max of all our choices and return it as our answer.\n\n# Complexity\n- Time complexity: O(N^3)\n<!-- Add your time complexity here, e.g. $$O(n)$$ -->\n\n- Space complexity: O(N^2)\n<!-- Add your space complexity here, e.g. $$O(n)$$ -->\n\n# Code\n```\nclass Solution {\n    int [][] dp ;\n    public int maxCoins(int[] nums) {\n        dp = new int[nums.length][nums.length];\n        for(int[] row : dp)\n            Arrays.fill(row,-1);\n        return solve(nums,0,nums.length-1);\n    }\n    public int solve(int [] nums,int i,int j)\n    {\n        if(i>j) return 0;\n        if(dp[i][j]!=-1)\n            return dp[i][j];\n        int max = 0;\n        for(int k = i;k<=j;k++)\n        {\n            int temp = solve(nums,i,k-1) + solve(nums,k+1,j)+nums[k]*(i-1<0?1:nums[i-1])*(j+1>=nums.length?1:nums[j+1]);\n            max = Math.max(max,temp);\n        }\n        return dp[i][j] = max;\n    }\n}\n```\n
['Java']