class Solution {
public:
    int n;
    int t[501][501]; // For memoization
    int solve(vector<int> &nums, int i, int j){
		// BASE CASES
		if(i > j)
			return 0;
        if(i == j){    // Only one element exists
            int temp = nums[i];
            if(i - 1 >= 0)  
                temp *= nums[i - 1];
            if(i + 1 < n)
                temp *= nums[i + 1];
            return temp;
        }
		if(t[i][j] != -1)  // Check if the solution is already stored for this subproblem
			return t[i][j];
        int ans = 0;
		
		// For all elements in the range i to j, we choose all of them one by one 
		// to make them the last balloon to be burst. 
        for(int k = i; k <= j; k++){
		
		    // Burst the kth balloon after bursting (i, k - 1) and (k + 1, j) balloons
            int temp = nums[k];
			
            if(j + 1 < n)  // As balloon j + 1 will become adjacent to k after bursting  k + 1 to j balloons
                temp *= nums[j + 1];
				
            if(i - 1 >= 0) // As balloon i- 1 will become adjacent to k after bursting  i  to k -1 balloons
                temp *= nums[i - 1];
				
			// Recursively solve the left and right subproblems and add their contribution
            temp += (solve(nums, i, k - 1) + solve(nums, k + 1, j));
			
			// If this choice of k yields a better answer
            ans = max(ans, temp);
        }
        return t[i][j] = ans;
    }
    
    int maxCoins(vector<int>& nums) {
        memset(t, -1, sizeof(t));
		
        // Insert two dummy balloons of value 1 to handle the balloons on the corner.
		vector<int> arr = {1};
        for(int x: nums) 
			arr.push_back(x);
        arr.push_back(1);
        n = arr.size();
		
		//Start from i = 1 and j = arr.size() - 2 since first and last balloons are dummy.
        return solve(arr, 1, arr.size() - 2);
    }
};

public int maxCoins(int[] nums) {
    int[][] dp = new int[nums.length][nums.length];
    return maxCoins(nums, 0, nums.length - 1, dp);
}

public int maxCoins(int[] nums, int start, int end, int[][] dp) {
    if (start > end) {
        return 0;
    }
    if (dp[start][end] != 0) {
        return dp[start][end];
    }
    int max = nums[start];
    for (int i = start; i <= end; i++) {
        int val = maxCoins(nums, start, i - 1, dp) + 
                  get(nums, i) * get(nums, start - 1) * get(nums, end + 1) + 
                  maxCoins(nums, i + 1, end, dp);
                  
        max = Math.max(max, val);
    }
    dp[start][end] = max;
    return max;
}

public int get(int[] nums, int i) {
    if (i == -1 || i == nums.length) {
        return 1;
    }
    return nums[i];
}
 

class Solution:
    def maxCoins(self, A):
        A, n = [1] + A + [1], len(A) + 2
        dp = [[0] * n for _ in range(n)]
        
        for i in range(n - 2, -1, -1):
            for j in range(i + 2, n):
                dp[i][j] = max(A[i]*A[k]*A[j] + dp[i][k] + dp[k][j] for k in range(i + 1, j))
        
        return dp[0][n-1]