Python程序：查找k个和最大的子列表，并按升序返回这些和

假设我们有一个名为nums的数字列表，以及另一个值k，我们需要找到k个和最大的子列表，并按非递减顺序返回这些和。

因此，如果输入类似于nums = [2, 4, 5, -100, 12, -30, 6, -2, 6] k = 3，则输出将为[10, 11, 12]，因为我们有这3个和最大的子列表：[6, -2, 6]、[2, 4, 5]、[12]。

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

• ps := 一个大小为nums大小+1的列表，并用0填充
• 对于每个索引i和值v nums，执行以下操作：
  • ps[i + 1] := v + ps[i]
• hp := 一个新的列表
• 对于范围从0到ps大小的i，执行以下操作：
  • 对于范围从i+1到ps大小的j，执行以下操作：
    • 将-(ps[j] - ps[i])插入ps堆中
• res := 弹出ps堆中的所有元素并反转它们
• 返回res

让我们看看下面的实现，以便更好地理解：

示例

 在线演示

from heapq import heappop, heappush
class Solution:
   def solve(self, nums, k):
      ps = [0 for _ in range(len(nums) + 1)]
      for i, v in enumerate(nums):
         ps[i + 1] = v + ps[i]
      hp = []
      for i in range(len(ps)):
         for j in range(i + 1, len(ps)):
            heappush(hp, -(ps[j] - ps[i]))
            return list(reversed([-heappop(hp)
      for _ in range(k)]))
ob = Solution()
nums = [2, 4, 5, -100, 12, -30, 6, -2, 6] k = 3
print(ob.solve(nums, k))

输入

[2, 4, 5, -100, 12, -30, 6, -2, 6],3

输出

[10, 11, 12]

Arnab Chakraborty

更新于: 2020年11月19日

124次浏览

开启你的职业生涯

通过完成课程获得认证

立即开始