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

假设我们有一个堆栈列表和一个整数k。我们必须找到从堆栈的任意组合中准确弹出k个元素可以实现的最大和。

因此，如果输入就像stacks = [[50，-4，-15]，[2]，[6，7，8]]，k = 4，那么输出将为39，因为我们可以弹出所有从第一个堆栈中取出3个元素，然后弹出最后一个堆栈中的最后一个元素，得到-15 + -4 + 50 + 8 = 39。

为了解决这个问题，我们将遵循以下步骤-

• 定义一个功能rec()。这需要我，n

• 如果n与k相同，则

• 返回0

• 如果n> k，则

• 返回负无穷大

• 如果我与堆栈数相同，则

• 返回负无穷大

• 如果我与堆栈数相同-1，则

• 返回stack [i]元素的最后总和

• 返回负无穷大

• 需要：= k-n

• 如果需要>堆栈的元素计数[i]，则

• 除此以外，

• res：= -math.inf，su：= 0

• 对于堆栈范围大小的sti [i]-1到0，

  减少1，做

• su：= su +堆栈[i，sti]

• localres：= su + rec（i + 1，n +堆栈大小[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