用 Python 编写程序，从堆栈列表中查找弹出的 k 个元素的最大和

pythonserver side programmingprogramming更新于 2026/1/17 7:08:17

假设我们有一个堆栈列表和一个整数 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 相同，则
- 需要 := k - n
- 如果需要 > stacks[i] 的元素数量，然后
  - 返回负无穷大
- 否则，
  - 返回 stack[i] 元素的总和，最后需要的元素数量
res := -math.inf, su := 0
对于 stacks[i] 大小范围为 - 1 到 0 的 sti，
减少 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))