ধরুন আমাদের একটি পূর্ণসংখ্যা অ্যারে A আছে, আমাদের অ্যারেটিকে সর্বাধিক K দৈর্ঘ্যের (সংলগ্ন) সাবয়ারেতে পার্টিশন করতে হবে। পার্টিশন করার পরে, প্রতিটি সাবয়ারের মান পরিবর্তন করে সেই সাবয়ারের সর্বোচ্চ মান হয়ে যায়। পার্টিশন করার পরে আমাদের প্রদত্ত অ্যারের বৃহত্তম যোগফল খুঁজে বের করতে হবে। সুতরাং যদি ইনপুট হয় [1, 15, 7, 9, 2, 5, 10] এবং k =3, তাহলে আউটপুট হবে 84। এর কারণ হল অ্যারেটি [15, 15, 15, 9, 10, 10] হয়ে যায়। , 10]
এটি সমাধান করতে, আমরা এই পদক্ষেপগুলি অনুসরণ করব -
- A এর মতো দৈর্ঘ্যের একটি অ্যারে ডিপি করুন এবং এটি 0 দিয়ে পূরণ করুন
- আমি 0 থেকে A - 1 এর দৈর্ঘ্যের মধ্যে
- dp[i] =A[i] + dp[i - 1] যদি i – 1>=0 অন্যথায় 0
- temp :=A[i] 1 থেকে k – 1
- যদি i – j>=0
- সূচক :=i – j
- temp :=তাপমাত্রার সর্বোচ্চ এবং A[i - j]
- যদি সূচক – 1>=0, তারপর
- dp[i] :=dp[i] এবং (temp*(i – index + 1) + dp[index - 1])
- অন্যথায় dp[i] :=সর্বাধিক dp[i] এবং 0
- পরিসরে j-এর জন্য
আরো ভালোভাবে বোঝার জন্য আসুন নিচের বাস্তবায়ন দেখি -
উদাহরণ
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
আউটপুট
84
