题目描述

数组 nums 表示一排气球上的数字。每次戳破第 i 个当前气球，可获得“它左侧相邻值 × 自身值 × 右侧相邻值”枚硬币；如果某一侧已经越过边界，该侧按数值 1 计算。

需要戳破所有气球，请返回能够获得的最大硬币数。

示例

输入: [3,1,5,8]
输出: 167
解释：
nums = [3,1,5,8] --> [3,5,8] --> [3,8] --> [8] --> []
coins =  3*1*5    +   3*5*8   +  1*3*8  + 1*8*1 = 167

输入: [1,5]
输出: 10

数据范围

• n == nums.length
• 1 <= n <= 300
• 0 <= nums[i] <= 100

代码框架

class Solution {
public:
    int maxCoins(vector<int>& nums) {
        // 请实现
    }
};