পাইথনে পার্টিশন অ্যারে ফর ম্যাক্সিমাম সম

একটি ইন্টিজার অ্যারে A দেওয়া আছে। অ্যারেটি কন্টিগুয়াস সাবঅ্যারেয়ে পার্টিশন করতে হবে যাতে প্রতিটি সাবঅ্যারের দৈর্ঘ্য সর্বোচ্চ K হয়। পার্টিশনের পর প্রতিটি সাবঅ্যারের সব ভ্যালু সেটির ম্যাক্সিমাম ভ্যালুতে বদলে যাবে। পার্টিশনের পর অ্যারেটির সর্বোচ্চ যোগফল বের করতে হবে।

ইনপুট [1, 15, 7, 9, 2, 5, 10] এবং k = 3 হলে আউটপুট 84। কারণ অ্যারেটি হয়ে যায় [15, 15, 15, 9, 10, 10, 10]।

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

dp নামের অ্যারে A-এর দৈর্ঘ্যের সমান 0 দিয়ে ফিল করুন
i = 0 থেকে len(A)-1 পর্যন্ত লুপ:
- dp[i] = A[i] + (dp[i-1] যদি i-1 >= 0 অন্যথায় 0)
- temp := A[i]
- j = 1 থেকে K-1 পর্যন্ত লুপ:
  - যদি i-j >= 0:
    - index := i-j
    - temp := max(temp, A[i-j])
    - যদি index-1 >= 0: dp[i] = max(dp[i], temp*(i-index+1) + dp[index-1])
    - অন্যথায়: dp[i] = max(dp[i], 0)
dp[-1] রিটার্ন

উদাহরণ

class Solution(object):
    def maxSumAfterPartitioning(self, A, K):
        dp = [0 for i in range(len(A))]
        for i in range(len(A)):
            dp[i] = A[i] + (dp[i-1] if i-1 >= 0 else 0)
            temp = A[i]
            for j in range(1, K):
                if i-j >= 0:
                    index = i-j
                    temp = max(temp, A[i-j])
                    dp[i] = max(dp[i], temp*(i-index+1) + (dp[index-1] if index-1 >= 0 else 0))
        return dp[-1]

ob = Solution()
print(ob.maxSumAfterPartitioning([1,15,7,9,2,5,10], 3))

ইনপুট

[1,15,7,9,2,5,10] 3