题解 | 打气球的最大分数

package main

import (
	"bufio"
	"fmt"
	"os"
	"strconv"
)

func main() {
	for {
		scanner := bufio.NewScanner(os.Stdin)

		// 设置大缓冲区，防止大输入时出错
		buf := make([]byte, 1024*1024) // 1MB
		scanner.Buffer(buf, 1024*1024)
		scanner.Split(bufio.ScanWords) // 按单词扫描（空格、换行等分隔）

		// 读取第一行：n
        var num int
		n, _ := fmt.Scan(&num)
		if n == 0 {
			break
		} else {
			arr := make([]int, num)
			for i := 0; i < len(arr); i++ {
				scanner.Scan()
				arr[i], _ = strconv.Atoi(scanner.Text())

			}
			fmt.Println(process(arr))
		}
	}
}

func process(arr []int) int {
	nums := make([]int, len(arr)+2)
	nums[0], nums[len(nums)-1] = 1, 1
	copy(nums[1:], arr)

	dp := make([][]int, len(nums))
	for i := 0; i < len(dp); i++ {
		dp[i] = make([]int, len(nums))
	}
   // 开区间的解法，和闭区间不一样
	for length := 2; length < len(nums); length++ {
		for i := 0; i+length < len(nums); i++ {
			j := i + length
			for k := i + 1; k < j; k++ {
				dp[i][j] = max(dp[i][j], nums[i]*nums[k]*nums[j]+dp[i][k]+dp[k][j])
			}
		}
	}
	return dp[0][len(nums)-1]
}

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