পাইথনে বৃহত্তম K সাবলিস্টের যোগফল খুঁজে বের করার জন্য প্রোগ্রাম

ধরুন আমাদের কাছে সংখ্যার একটি তালিকা আছে যাকে nums বলা হয়, এবং আরেকটি মান k, যা k বারের সমন্বিত সংখ্যাগুলির একটি বড় তালিকা উপস্থাপন করে। আমাদের সবচেয়ে বড় যোগফলের সাথে সংলগ্ন সাবলিস্টের যোগফল খুঁজে বের করতে হবে।

সুতরাং, ইনপুট যদি nums =[1, 3, 4, -5], k =1 এর মত হয়, তাহলে আউটপুট হবে 11, যেমন আমরা [2, 4, 5] এর মত সাবলিস্ট নিতে পারি।

এটি সমাধান করতে, আমরা এই পদক্ষেপগুলি অনুসরণ করব -

s :=ans :=lo :=0
0 থেকে সর্বনিম্ন k এবং 2 রেঞ্জের সমস্ত মানের জন্য, করুন
- সংখ্যায় প্রতিটি x এর জন্য, করুন
  - s :=s + x
  - lo :=সর্বনিম্ন lo, s
  - উত্তর :=সর্বাধিক উত্তর, s - lo
উত্তর দিন + সর্বাধিক 0 এবং সংখ্যার সমস্ত উপাদানের যোগফল * সর্বাধিক 0 এবং (k - 2)

আরো ভালোভাবে বোঝার জন্য আসুন নিচের বাস্তবায়ন দেখি -

উদাহরণ

class Solution:
   def solve(self, nums, k):
      s = ans = lo = 0
      for _ in range(min(k, 2)):
         for x in nums:
            s += x
            lo = min(lo, s)
         ans = max(ans, s - lo)
      return ans + max(0, sum(nums)) * max(0, (k - 2))
ob = Solution()
nums = [2, 4, 5, -4]
k = 1
print(ob.solve(nums, k))

ইনপুট

[2, 4, 5, -4], 1