पायथन में 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 := आकार len(nums)+1 की सूची, 0 से भरी (प्रीफिक्स सम)
• ps[i+1] = nums[i] + ps[i] प्रत्येक i के लिए
• hp := एक मैक्स हीप (नेगेटिव मान स्टोर करके)
• सभी i < j के लिए: -(ps[j]-ps[i]) को हीप में डालें
• हीप से k तत्व पॉप करें, नेगेट करें, उल्टा करें और लौटाएं

उदाहरण कोड

from heapq import heappop, heappush

class Solution:
    def solve(self, nums, k):
        ps = [0] * (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]))
        res = []
        for _ in range(k):
            res.append(-heappop(hp))
        return list(reversed(res))

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]