C++ sol. Top Down Dp
class Solution {\npublic:\n\t\t\tint dp[502][502];\n\t\t\n\tint fun(vector&v , int l , int r){\n\t\t\tif(dp[l][r]!=-1){\n\t\t\t\treturn dp[l][r];\n\t\t\t}\n\t\t
class Solution {\npublic:\n\t\t\tint dp[502][502];\n\t\t\n\tint fun(vector<int>&v , int l , int r){\n\t\t\tif(dp[l][r]!=-1){\n\t\t\t\treturn dp[l][r];\n\t\t\t}\n\t\t\tint ans = 0 ;\n\t\t\tfor(int i=l ; i<=r ; i++){\n\t\t\t\tans = max( ans , v[i]*(l!=0?v[l-1]:1)*(r!=v.size()-1?v[r+1]:1) + (i>0?fun(v,l,i-1):0) + (i<v.size()-1?fun(v,i+1,r):0) );\n\t\t}\n        \n        return dp[l][r]=ans ;\n    }\n    int maxCoins(vector<int>& nums) {\n        memset(dp , -1 , sizeof(dp));\n        int ans = fun(nums , 0 , nums.size()-1);\n        \n        return ans ;\n    }\n};
['C']