在Python中找到最大点数的程序剔除

假设我们有一个正数列表。现在，我们可以删除任何连续的长度为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：=left
当left2
- left2：=left2 + 1
t：=t + left2 − left + 1
左：=left2 + 1
points：=t的平方+ dp（left，right，0）
for mid in range left to right + 1, do
- if nums [mid] is same as num, then
  - points：=maximum of（points，dp（left，mid − 1，0）+ dp（mid，right，t））
返回点数
从主函数中，我们执行以下操作−
打印（DP（0，nums的大小 − 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]))