111213141516171819202122232425262728293031323334353637

import java.util.*;

public class Solution {
    static int maxCoins(ArrayList<Integer> a) {
        int n = a.size();
        
        // Add 1 to the beginning and end of the array
        a.add(0, 1);
        a.add(1);
        
        // Create a 2D DP array
        int[][] dp = new int[n + 2][n + 2];

        // Iterate from the end to the beginning
        for (int i = n; i >= 1; i--) {
            for (int j = 1; j <= n; j++) {
                if (i > j) continue;
                int maxi = Integer.MIN_VALUE;
                
                // Iterate through possible indices to split the array
                for (int ind = i; ind <= j; ind++) {
                    int cost = a.get(i - 1) * a.get(ind) * a.get(j + 1) +
                               dp[i][ind - 1] + dp[ind + 1][j];
                    maxi = Math.max(maxi, cost);
                }
                dp[i][j] = maxi;
            }
        }
        return dp[1][n];
    }

    public static void main(String[] args) {
        ArrayList<Integer> a = new ArrayList<>(Arrays.asList(3, 1, 5, 8));
        int ans = maxCoins(a);
        System.out.println(ans);
    }
}

123456789101112131415161718192021222324252627282930

def maxCoins(a):
    n = len(a)
    
    # Extend the list 'a' with 1s at both ends
    a.insert(0, 1)
    a.append(1)

    # Create a 2D DP table initialized with 0s
    dp = [[0] * (n + 2) for _ in range(n + 2)]

    # Loop from the end of 'a' to the beginning
    for i in range(n, 0, -1):
        for j in range(1, n + 1):
            if i > j:
                continue
            maxi = float('-inf')
            
            # Iterate through the balloons from 'i' to 'j'
            for ind in range(i, j + 1):
                cost = a[i - 1] * a[ind] * a[j + 1] + dp[i][ind - 1] + dp[ind + 1][j]
                maxi = max(maxi, cost)
            
            dp[i][j] = maxi
    
    return dp[1][n]

if __name__ == "__main__":
    a = [3, 1, 5, 8]
    ans = maxCoins(a)
    print(ans)

1234567891011121314151617181920212223242526272829303132333435363738394041424344

function findMaxCoins(a) {
    // Add 1 to the beginning and end of the array 'a'
    a.unshift(1);
    a.push(1);
    
    // Get the length of the array 'a'
    let n = a.length;