在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：一个填充为0的大小为nums的长度的列表+ 1
对于每个索引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

让我们看以下实现，以获得更好的理解 –

更多Python相关文章，请阅读：Python 教程

示例

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))