পাইথনে সর্বাধিক দুটি নন-ওভারল্যাপিং সাবলিস্টের যোগফল খুঁজে বের করার প্রোগ্রাম

ধরুন আমাদের কাছে nums নামক সংখ্যার একটি তালিকা এবং দুটি মান x এবং y আছে, আমাদের সংখ্যাগুলিতে দুটি অ-ওভারল্যাপিং সাবলিস্টের সর্বাধিক যোগফল খুঁজে বের করতে হবে যার দৈর্ঘ্য x এবং y আছে।

সুতরাং, যদি ইনপুট nums =[3, 2, 10, -2, 7, 6] x =3 y =1 এর মত হয়, তাহলে আউটপুট হবে 22, দৈর্ঘ্য 3 সহ সাবলিস্ট হিসাবে আমরা [3, 2, নির্বাচন করি। 10] এবং অন্যটির জন্য আমরা [7] নির্বাচন করি।

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

P :=একক উপাদান 0 সহ একটি তালিকা
এ প্রতিটি x এর জন্য, করুন
- P এর শেষে সন্নিবেশ করুন (P + x এর শেষ উপাদান)
একটি ফাংশন সংজ্ঞায়িত করুন solve()। এটি len1, len2
Q :=0 থেকে P - len1 এর আকারের প্রতিটি i এর জন্য উপাদান (P[i + len1] - P[i]) সহ একটি তালিকা
উপসর্গ :=Q এর একটি অনুলিপি
আমি 0 থেকে প্রিফিক্সের আকার - 1 এর মধ্যে, কর
- উপসর্গ[i + 1] :=সর্বাধিক উপসর্গ[i + 1] এবং উপসর্গ[i]
উত্তর :=-অনন্ত
এর জন্য len1 থেকে P - len2 এর আকারের মধ্যে, do
- বাম :=উপসর্গ[i - len1]
- ডান :=P[i + len2] - P[i]
- উত্তর :=সর্বাধিক উত্তর এবং (বাম + ডান)
উত্তর ফেরত দিন
প্রধান পদ্ধতি থেকে নিম্নলিখিতগুলি করুন -
সর্বোচ্চ রিটার্ন (len1, len2) , solve(len2, len1)

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

উদাহরণ

class Solution:
   def solve(self, A, len1, len2):
      P = [0]
      for x in A:
         P.append(P[-1] + x)
      def solve(len1, len2):
         Q = [P[i + len1] - P[i] for i in range(len(P) - len1)]
         prefix = Q[:]
         for i in range(len(prefix) - 1):
            prefix[i + 1] = max(prefix[i + 1], prefix[i])
            ans = float("-inf")
            for i in range(len1, len(P) - len2):
               left = prefix[i - len1]
               right = P[i + len2] - P[i]
            ans = max(ans, left + right)
            return ans
         return max(solve(len1, len2), solve(len2, len1))
ob = Solution()
nums = [3, 2, 10, -2, 7, 6]
x = 3
y = 1
print(ob.solve(nums, x, y))

ইনপুট

[3, 2, 10, -2, 7, 6], 3, 1