include <iostream>

include <vector>

using namespace std;

class Solution {
public:
int maxCoins(vector<int>& nums) {
if (nums.empty()) {
return 0;
}
int len = nums.size();
vector<vector<int> > dp(len, vector<int>(len, 0));
for (int i = 0; i < len; i++) {
dp[i][i] = nums[i];
}

    for (int wide = 2; wide <= len; wide++) {
        for (int i = 0; i + wide - 1 < len; i++) {
            int j = i + wide - 1;
            for(int m = i; m <= j; m++) {
                if (m == i) {
                    dp[i][j] = max(dp[i][j], (m == 0 ? 1 : nums[m - 1]) * ((j + 1 > len - 1) ? 1 : nums[j + 1]) + dp[m + 1][j]);
                }
                else if (m == j) {
                    dp[i][j] = max(dp[i][j], (m == len - 1 ? nums[i - 1] : 1) * ((j + 1 > len - 1) ? 1 : nums[j + 1]) + dp[m + 1][j]);
                }
                else if(m == j) {
                    dp[i][j] = max(dp[i][j], dp[i][m - 1] + nums[m - 1] * dp[j][j]);
                }
                else {
                    dp[i][j] = max(dp[i][j], dp[i][m] + dp[m + 1][j] + nums[m] * nums[m - 1] * nums[m + 1]);
                }
            }
        }
    }
    return dp[0][len - 1];
}

};

int main() {
Solution* s = new Solution();
vector<int> nums = {7, 2, 9};
int maxcoin = s -> maxCoins(nums);
cout << maxcoin << endl;
// vector<int> a;
// if (a.empty()) {
// cout << "a is empty" << endl;
// }
}