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

একটি লিস্ট nums এবং একটি মান k দেওয়া আছে। লিস্ট থেকে আকার k-এর ৩টি নন-ওভারল্যাপিং সাবলিস্ট বেছে নিতে হবে যাতে তাদের মোট যোগফল সর্বোচ্চ হয়।

উদাহরণস্বরূপ, nums = [2, 2, 2, -6, 4, 4, 4, -8, 3, 3, 3], k = 3 হলে আউটপুট ২৭, কারণ সাবলিস্টগুলো: [2,2,2], [4,4,4], [3,3,3] → যোগফল ৬+১২+৯=২৭।

সমাধানের পদ্ধতি (প্রিফিক্স সাম + স্লাইডিং উইন্ডো + প্রিফিক্স/সাফিক্স ম্যাক্স)

P = প্রিফিক্স সাম অ্যারে (P[0]=0)।
Q[i] = P[i+k] - P[i] = ইন্ডেক্স i-থেকে শুরু হওয়া সাবঅ্যারে-র যোগফল।
prefix[i] = Q[0..i]-র ম্যাক্স, suffix[i] = Q[i..end]-র ম্যাক্স।
মধ্যম সাবঅ্যারে i (রেঞ্জ k .. len(Q)-k-1) ধরে বাম ও ডানের সেরা সাবঅ্যারে নিয়ে মোট যোগফল বের করুন: Q[i] + prefix[i-k] + suffix[i+k]।
সর্বোচ্চ মান রিটার্ন করুন।

পাইথন কোড উদাহরণ

class Solution:
    def solve(self, A, K):
        P = [0]
        for x in A:
            P.append(P[-1] + x)
        Q = [P[i+K] - P[i] for i in range(len(P) - K)]
        prefix = Q[:]
        suffix = Q[:]
        for i in range(len(Q) - 1):
            prefix[i+1] = max(prefix[i+1], prefix[i])
            suffix[~(i+1)] = max(suffix[~(i+1)], suffix[~i])
        return max(Q[i] + prefix[i-K] + suffix[i+K] for i in range(K, len(Q) - K))

ob = Solution()
nums = [2, 2, 2, -6, 4, 4, 4, -8, 3, 3, 3]
k = 3
print(ob.solve(nums, k))

ইনপুট

[2, 2, 2, -6, 4, 4, 4, -8, 3, 3, 3], 3