给定一个数组arr,长度为n。代表排有分数的气球。 每打爆一个气球都能获得分数,假设打爆气球的分数为X,获得分数的规则如下: 1)如果被打爆气球的左边有没被打爆的气球,找到离被打爆气球最近的气球,假设分数为L:如果被打爆气球的右边有没被打爆的气球,找到离被打爆气球最近的气球,假设分数为R.获得分数为L*X*R 2)如果被打爆的气球的左边有没被打爆的气球,找到离被打爆气球最近的气球,假设分数为L:如果被打爆气球的右边所有气球都已经被打爆,获得分数为L*X。 3)如果被打爆气球的左边所有的气球都已经被打爆:如果被打爆气球的右边有没被打爆的气球,找到离被打爆气球最近的气球。获得分数为X*R. 4)如果被打爆气球的左边和右边所有的气球都已经被打爆。获得分数为X。 目标是打爆所有气球,获得每次打爆的分数。通过选择打爆气球的顺序,可以得到不同的总分,请返回能获得的最大分数。
输入描述:
输出包括两行,第一行包括一个整数n(0=n=500),第二行包括n个整数,代表数组arr (1=arr[i]=100)。


输出描述:
输出包括一个整数,代表可能获得的最大分数。
示例1

输入

3
3 2 5

输出

50

说明

2->1->3  3*2*5+3*5+5=50 
示例2

输入

8
23 4 45 65 23 43 54 56

输出

639019

备注:
时间复杂度,空间复杂度。
加载中...