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 次瀏覽

開啟您的職業生涯

完成課程，獲得認證

開始學習
廣告