你在游乐场发现⼀个玩具枪射击气球的游戏，游戏规则如下：有 n 个气球，编号为 0 到 n - 1 ，每个气球上都标有⼀个数字，这些数字存在数组 nums 中。每打破第 i 个气球，你可以 获得 nums[i - 1] \times nums[i] \times nums[i + 1] 枚硬币，求所能获得硬币的最大数量。

这里的 i - 1 和 i + 1 代表和 i 相邻的两个气球的序号。如果 i - 1 或 i + 1 超出了数组 的边界，那么就当它是⼀个数字为 1 的气球。

第⼀行包含⼀个整数 n，代表 nums 数组的长度；

第二行包含 n 个整数，代表 nums 数组的元素，以空格隔开。

⼀行，包含⼀个整数，代表获取的最大的硬币数量。

【样例1说明】

nums = [3,1,5,8] --> [3,5,8] --> [3,8] --> [8] --> []

coins = 3 \times 1 \times 5 + 3 \times 5 \times 8 + 1 \times 3 \times 8 + 1 \times 8 \times 1 = 167

【数据范围】

1 \leq n \leq 300

0 \leq 每个气球上标的数字 \leq 100

23年泰州市赛

市赛