package main

import (
    "fmt"
)

func main() {
    arr := []int{2, 2, 2}
    ret := maxCoins1(arr)
    fmt.Println(ret)

    ret = maxCoins2(arr)
    fmt.Println(ret)
}

func maxCoins1(arr []int) int {
    if len(arr) == 0 {
        return 0
    }
    if len(arr) == 1 {
        return arr[0]
    }
    N := len(arr)
    help := make([]int, N+2)
    help[0] = 1
    help[N+1] = 1
    for i := 0; i < N; i++ {
        help[i+1] = arr[i]
    }
    return process(help, 1, N)
}

// 打爆arr[L..R]范围上的所有气球，返回最大的分数
// 假设arr[L-1]和arr[R+1]一定没有被打爆
func process(arr []int, L int, R int) int {
    if L == R { // 如果arr[L..R]范围上只有一个气球，直接打爆即可
        return arr[L-1] * arr[L] * arr[R+1]
    }
    // 最后打爆arr[L]的方案，和最后打爆arr[R]的方案，先比较一下
    max := getMax(arr[L-1]*arr[L]*arr[R+1]+process(arr, L+1, R),
        arr[L-1]*arr[R]*arr[R+1]+process(arr, L, R-1))
    // 尝试中间位置的气球最后被打爆的每一种方案
    for i := L + 1; i < R; i++ {
        max = getMax(max, arr[L-1]*arr[i]*arr[R+1]+process(arr, L, i-1)+process(arr, i+1, R))
    }
    return max
}

func maxCoins2(arr []int) int {
    if len(arr) == 0 {
        return 0
    }
    if len(arr) == 1 {
        return arr[0]
    }
    N := len(arr)
    help := make([]int, N+2)
    help[0] = 1
    help[N+1] = 1
    for i := 0; i < N; i++ {
        help[i+1] = arr[i]
    }
    dp := make([][]int, N+2)
    for i := 0; i < N+2; i++ {
        dp[i] = make([]int, N+2)

    }
    for i := 1; i <= N; i++ {
        dp[i][i] = help[i-1] * help[i] * help[i+1]
    }
    for L := N; L >= 1; L-- {
        for R := L + 1; R <= N; R++ {
            ans := help[L-1]*help[L]*help[R+1] + dp[L+1][R]
            ans = getMax(ans, help[L-1]*help[R]*help[R+1]+dp[L][R-1])
            for i := L + 1; i < R; i++ {
                ans = getMax(ans, help[L-1]*help[i]*help[R+1]+dp[L][i-1]+dp[i+1][R])
            }
            dp[L][R] = ans
        }
    }
    return dp[1][N]
}

func getMax(a int, b int) int {
    if a > b {
        return a
    } else {
        return b
    }
}