Python程式：查詢“有效”陣列的最大值

假設我們有一個包含n個整數的陣列'nums'。'nums'中的每個值代表其“能量”。如果陣列的長度大於2且陣列的第一個和最後一個值相等，則該陣列將被評估為“有效”。我們必須透過從陣列中刪除元素來使陣列有效，以便其餘元素可以滿足條件。作為輸出，我們返回透過新增陣列的所有能量值獲得的陣列的最大可能能量值。

因此，如果輸入類似於nums = [3, 4, 5, 3, 4]，則輸出將為16。

如果我們從陣列nums中移除第一個值3，則它變為[4, 5, 3, 4]。這是一個有效的陣列，能量之和為4 + 5 + 3 + 4 = 16。這是從給定輸入中獲得的任何有效陣列的最大可能和。

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

  • table := 一個新的對映

  • prefix := 一個初始化值為0的新列表

  • negative := 一個初始化值為0的新列表

  • 對於nums中的每個索引i和值j，執行以下操作：

    • 如果table中不存在j，則

      • table[j] := 一個新的對(i, 0)

      • 否則，

        • table[j, -1] := i

      • 向prefix新增一個新元素，該元素等於prefix的最後一個元素 + j

      • 複製negative的最後一個元素

      • 如果j < 0，則

        • negative的最後一個元素 := negative的最後一個元素 + j

  • ans := 負無窮大

  • 對於table的所有值中的每個對(i,j)，執行以下操作：

    • 如果j不等於0，則

      • sm1 := prefix[j+1] - prefix[i]

      • 如果j > i+1，則

        • sm2 := negative[j] - negative[i+1]

      • 否則，

        • sm2 := 0

      • ans := (ans, sm1 - sm2)中的最大值

  • 返回ans

示例

讓我們檢視以下實現以獲得更好的理解：

def solve(nums):
   table = {}
   prefix = [0]
   negative = [0]
   for i, j in enumerate(nums):
      if j not in table:
         table[j] = [i, 0]
      else:
         table[j][-1] = i
      prefix += prefix[-1] + j,
      negative += negative[-1],
      if j < 0:
         negative[-1] += j

   ans = float('-inf')
   for i,j in table.values():
      if j != 0:
         sm1 = prefix[j+1] - prefix[i]
         sm2 = negative[j] - negative[i+1] if j > i+1 else 0
         ans = max(ans, sm1 - sm2)
   return ans

print(solve([3, 4, 5, 3, 4]))

輸入

[3, 4, 5, 3, 4]

輸出

16

更新於： 2021年10月8日

185 次檢視

開啟您的 職業生涯

透過完成課程獲得認證

開始
廣告