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

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

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

সমাধানের ধাপসমূহ:

P := [0] (একটি এলিমেন্টযুক্ত তালিকা)
প্রতিটি x এর জন্য A-এ, P[-1] + x কে P-র শেষে ঢুকান (প্রিফিক্স সাম)।
একটি solve() ফাংশন ডিফাইন করুন যা len1, len2 নেবে।
- Q := [P[i+len1] - P[i] for i in range(len(P)-len1)]
- prefix := Q কপি
- i কে ০ থেকে len(prefix)-1 পর্যন্ত লুপ চালান:
  - prefix[i+1] = max(prefix[i+1], prefix[i])
- ans := -infinity
- i কে len1 থেকে len(P)-len2 পর্যন্ত লুপ চালান:
  - left := prefix[i-len1]
  - right := P[i+len2] - P[i]
  - ans := max(ans, left+right)
- ans রিটার্ন করুন।
মূল মেথড থেকে max(solve(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

আউটপুট