给定一个数组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)。
输出描述:
输出包括一个整数,代表可能获得的最大分数。
备注:
时间复杂度,空间复杂度。
加载中...