โปรแกรมหา k สับลิสต์ผลรวมมากสุดและคืนผลรวมเรียงน้อยไปมากใน Python

สมมติว่ามีรายการตัวเลข nums และค่า k ต้องการหา k สับลิสต์ที่ผลรวมมากสุด คืนผลรวมเรียงจากน้อยไปมาก

ตัวอย่าง: nums = [2,4,5,-100,12,-30,6,-2,6], k=3 ผลลัพธ์ [10,11,12] จากสับลิสต์ [6,-2,6], [2,4,5], [12]

ขั้นตอนการแก้ปัญหา

1. สร้าง prefix sum ps ขนาด len(nums)+1
2. ใช้ max-heap (เก็บค่าลบ) เก็บผลรวมทุก subarray: -(ps[j]-ps[i])
3. Pop k ครั้ง, กลับเครื่องหมาย, กลับลำดับ

ตัวอย่างโค้ด

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]