মান লক্ষ্য করুন আমাদের কাছে একটি সংখ্যার তালিকা 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] (যোগফল ১২)।
ps := [0] * (len(nums) + 1)(প্রিফিক্স সাম অ্যারে)- প্রতিটি ইনডেক্স
iএবং ভ্যালুvএর জন্যnums-এ:ps[i+1] := v + ps[i]
hp := [](হিপ)iকে ০ থেকেlen(ps)পর্যন্ত লুপ চালান:jকেi+1থেকেlen(ps)পর্যন্ত লুপ চালান:-(ps[j] - ps[i])কেhp-তে পুশ করুন (ম্যাক্স হিপ অনুকরণ)
res := hp-র সব এলিমেন্ট পপ করে রিভার্স করুন।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]
