Python程式：查詢從棧列表中彈出k個元素的最大和

假設我們有一系列棧和一個整數k。我們必須找到從任何棧的組合中彈出恰好k個元素所能達到的最大可能和。

因此，如果輸入類似於 stacks = [[50, -4, -15],[2],[6, 7, 8]], k = 4，則輸出將為39，因為我們可以從第一個棧彈出所有3個元素，並彈出最後一個棧的最後一個元素以獲得 -15 + -4 + 50 + 8 = 39。

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

  • 定義一個函式rec()。這將接收i，n

  • 如果n等於k，則

    • 返回0

  • 如果n > k，則

    • 返回負無窮大

  • 如果i等於棧的數量，則

    • 返回負無窮大

  • 如果i等於棧的數量 - 1，則

    • needed := k - n

    • 如果needed > stacks[i]的元素數量，則

      • 返回負無窮大

    • 否則，

      • 返回stack[i]最後needed個元素的總和

  • res := -math.inf, su := 0

  • 對於sti in range stacks[i]的大小 - 1 到 0，

    遞減1，執行

    • su := su + stacks[i, sti]

    • localres := su + rec(i + 1, n + stacks[i]的大小 - sti)

    • res := res和localres的最大值

  • 返回res和rec(i + 1, n)的最大值

  • 從主方法呼叫rec(0, 0)

讓我們看看下面的實現，以便更好地理解：

示例

import math

class Solution:
   def solve(self, stacks, k):
      def rec(i, n):
         if n == k:
            return 0
         if n > k:
            return -math.inf
         if i == len(stacks):
            return -math.inf
         if i == len(stacks) - 1:
            needed = k - n
            if needed > len(stacks[i]):
               return -math.inf
            else:
               return sum(stacks[i][-needed:])
         res, su = -math.inf, 0
         for sti in range(len(stacks[i]) - 1, -1, -1):
            su += stacks[i][sti]
            localres = su + rec(i + 1, n + len(stacks[i]) - sti)
            res = max(res, localres)
         return max(res, rec(i + 1, n))

      return rec(0, 0)

ob = Solution()
stacks = [
   [50, -4, -15],
   [2],
   [6, 7, 8]
]
k = 4
print(ob.solve(stacks, k))

輸入

[[50, -4, -15],[2],[6, 7, 8]], 4

輸出

39

更新於：2020年10月9日

瀏覽量：255

開啟你的職業生涯

完成課程獲得認證

開始學習
廣告
© . All rights reserved.