Python 程式查詢最大擦除值

假設我們有一個名為 nums 的陣列（僅包含正值），我們想要擦除一個包含唯一元素的子陣列。我們將獲得一個分數，即子陣列元素的總和。我們必須找到透過精確擦除一個子陣列可以獲得的最大分數。

因此，如果輸入類似於 nums = [6,3,2,3,6,3,2,3,6]，則輸出將為 11，因為這裡的最佳子陣列是 [6,3,2] 或 [2,3,6]，所以總和為 11。

為了解決這個問題，我們將遵循以下步驟 -

  • seen := 一個新的對映
  • ans := sum := 0
  • l := 0
  • 對於每個索引 r 和值 x nums，執行
    • 如果 x 出現在 seen 中，則
      • index := seen[x]
      • 當 l <= index 時，執行
        • 刪除 seen[nums[l]]
        • sum := sum - nums[l]
        • l := l + 1
    • seen[x] := r
    • sum := sum + x
    • ans := ans 和 sum 的最大值
  • 返回 ans

示例

讓我們看看以下實現以獲得更好的理解 -

def solve(nums):
   seen = dict()
   ans = sum = 0
   l = 0
   for r, x in enumerate(nums):
      if x in seen:
         index = seen[x]
         while l <= index:
            del seen[nums[l]]
            sum -= nums[l]
            l += 1

      seen[x] = r
      sum += x
      ans = max(ans, sum)
   return ans

nums = [6,3,2,3,6,3,2,3,6]
print(solve(nums))

輸入

[6,3,2,3,6,3,2,3,6]

輸出

11

更新於: 2021年10月6日

115 次檢視

開啟您的 職業生涯

透過完成課程獲得認證

開始學習
廣告