问:现在,在这里我们可以删除具有相同值的长度为t的任何连续子列表,并获得点t * t。要考虑的一个条件是,我们可以执行任意次此操作,直到列表为空。因此,我们必须确定可以获得的最大点数。
因此,如果输入类似于nums = [4、4、6、4、4],则输出将为17。
对于输出,我们可以首先删除长度为1并产生1 * 1 = 1点的6。然后我们可以得到列表[4,4,4,4],它的长度为4,产生4 * 4 = 16点。所以最后,我们可以得到17分。
为了解决这个问题,我们将遵循以下步骤-
定义一个函数dp()。这将需要左,右,t
如果left> right不为零,则
返回0
num:= nums [left]
left2:=左
而left2 <right和nums [left2 + 1]与num相同,
left2:= left2 +1
t:= t +左2 −左+ 1
左:=左2 +1
点:= t等于2 + dp(左,右,0)
从左到右+ 1的中间范围
如果nums [mid]与num相同,则
points:=最大(points,dp(left,mid-1,0)+ dp(mid,right,t))
返回点
从主要功能,我们执行以下操作-
print(dp(0,大小-1,0))
答:class Solution:
def solve(self, nums):
def dp(left, right, t):
if left > right:
return 0
num = nums[left]
left2 = left
while left2 < right and nums[left2 + 1] == num:
left2 += 1
t += left2 − left + 1
left = left2 + 1
points = t ** 2 + dp(left, right, 0)
for mid in range(left, right + 1):
if nums[mid] == num:
points = max(points, dp(left, mid − 1, 0) + dp(mid, right, t))
return points
return dp(0, len(nums) − 1, 0)
ob1 = Solution()
print(ob1.solve([4, 4, 6, 4, 4]))
输入值
[4, 4, 6, 4, 4]
输出量
17