Python程序：找出移除元素后可获得的最大点数

假设我们得到一个正数列表。现在，我们可以移除任意长度为t的连续子列表（子列表中的值都相同），并获得t * t的点数。可以进行多次移除操作，直到列表为空。我们需要确定可以获得的最大点数。

例如，如果输入是nums = [4, 4, 6, 4, 4]，则输出为17。

为了得到输出17，我们可以先移除6（长度为1），获得1 * 1 = 1点。然后移除[4, 4, 4, 4]（长度为4），获得4 * 4 = 16点。最终获得17点。

为了解决这个问题，我们将遵循以下步骤：

  • 定义一个函数dp()，它接受left、right、t作为参数。

  • 如果left > right，则

    • 返回0

  • num := nums[left]

  • left2 := left

  • 当left2 < right 且 nums[left2 + 1] 等于 num 时，执行

    • left2 := left2 + 1

  • t := t + left2 − left + 1

  • left := left2 + 1

  • points := t的平方 + dp(left, right, 0)

  • 对于mid从left到right+1的范围，执行

    • 如果nums[mid] 等于 num，则

      • points := max(points, dp(left, mid − 1, 0) + dp(mid, right, t))

  • 返回points

  • 在主函数中，我们执行以下操作：

  • print(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]))

输入

[4, 4, 6, 4, 4]

输出

17

更新于：2020年12月15日

214 次浏览

开启您的职业生涯

完成课程，获得认证

开始学习
广告