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.