一共有N个气球，编号是0到n-1，每个气球上面都印了一个数字，这些数字都按照气球的编号依次存在数组nums中。你的任务是吹爆所有的气球，如果你吹爆了编号为i的气球，
那么你将获得nums[left]*nums[i]*nums[right]的分值，这里的left和right分别代表编号i的左边的气球和右边的气球。如果编号i的气球爆了，那么它左边和右边的气球就变成了相邻的气球了。
吹气球的过程中你要使得获得的分值尽可能的大。

第一行，一个整数n，表示气球的数量。0≤n≤500
第二行，n个整数，分别表示n个气球的分值。0≤nums[i]≤100(假设nums[-1]=1,nums[n]=1;)

输出一行，一个整数，表示能够获取到的最大的分值

样例说明：
样例1:
nums = [4, 1, 5, 10]  吹爆分值为1的气球, 获得的分值是:4 * 1 * 5 = 20
nums = [4, 5, 10]      吹爆分值为5的气球, 获得的分值是:4 * 5 * 10 = 200 
nums = [4, 10]          吹爆分值为1的气球, 获得的分值是:1 * 4 * 10 = 40
nums = [10]               吹爆分值为10的气球, 获得的分值是:1 * 10 * 1 = 10
获得的总分值是: 20 + 200 + 40 + 10 = 270


样例2：
nums = [3, 1, 5]  吹爆分值为1的气球, 获得的分值是: 3 * 1 * 5 = 15
nums = [3, 5]      吹爆分值为3的气球, 获得的分值是: 1 * 3 * 5 = 15
nums = [5]          吹爆分值为5的气球, 获得的分值是: 1 * 5 * 1 = 5
获得的总分值是: 15 + 15 + 5  = 35

区间DP level6