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：=1 + numsのサイズのリストで、0で埋めます
• インデックスiと値vの数値ごとに、実行します
  • ps [i + 1]：=v + ps [i]
• hp：=新しいリスト
• 0からpsのサイズの範囲のiについては、
  • i + 1からpsのサイズまでの範囲のjについては、
    • -（ps [j] --ps [i]）をpsヒープに挿入します
• res：=psヒープ内のすべての要素をポップし、それらを反転します
• return 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]