মনে করুন আমাদের একটি ধনাত্মক সংখ্যার তালিকা দেওয়া হয়েছে। এখন, আমরা একই মান 갖고 একটি সম্মিলিত সাবলিস্ট t দৈর্ঘ্যের যেকোনো অংশ মুছে ফেলতে পারি এবং t * t পয়েন্ট পেতে পারি। একটি শর্ত বিবেচনা করতে হবে, আমরা তালিকা খালি না হওয়া পর্যন্ত যেকোনো সংখ্যকবার এটি করতে পারি। তাই আমাদের সর্বোচ্চ পয়েন্ট খুঁজে বের করতে হবে।
উদাহরণস্বরূপ, যদি ইনপুট হয় nums = [4, 4, 6, 4, 4], তবে আউটপুট হবে 17।
আউটপুটের জন্য, আমরা প্রথমে 6 কে মুছতে পারি যার দৈর্ঘ্য 1 এবং 1 * 1 = 1 পয়েন্ট দেয়। তারপর আমরা [4, 4, 4, 4] তালিকাটি নিতে পারি যার দৈর্ঘ্য 4 এবং 4 * 4 = 16 পয়েন্ট দেয়। সুতরাং, আমরা সর্বোচ্চ 17 পয়েন্ট পেতে পারি।
এটি সমাধান করতে আমরা নিচের ধাপগুলো অনুসরণ করব:
একটি dp() ফাংশন সংজ্ঞায়িত করুন। এটি left, right, t নিবে
যদি left > right নন-জিরো হয়, তবে
0 রিটার্ন করুন
num := nums[left]
left2 := left
যখন left2 < right এবং nums[left2 + 1] num-এর সমান, করুন
left2 := left2 + 1
t := t + left2 - left + 1
left := left2 + 1
points := t এর বর্গ + dp(left, right, 0)
mid = left থেকে right + 1 পর্যন্ত, করুন
যদি nums[mid] num-এর সমান হয়, তবে
points := points এবং dp(left, mid - 1, 0) + dp(mid, right, t)-এর সর্বোচ্চ
points রিটার্ন করুন
মূল ফাংশন থেকে, নিচের কাজটি করুন
dp(0, nums-এর আকার - 1, 0) প্রিন্ট করুন
বेहतर বোঝার জন্য নিচের বাস্তবায়নটি দেখুন:
উদাহরণ
class Solution: def solve(self, nums): def dp(left, right, t): if left > right: return 0 num = nums[left] left2 = left while left2 < right and nums[left2 + 1] == num: left2 += 1 t += left2 - left + 1 left = left2 + 1 points = t ** 2 + dp(left, right, 0) for mid in range(left, right + 1): if nums[mid] == num: points = max(points, dp(left, mid - 1, 0) + dp(mid, right, t)) return points return dp(0, len(nums) - 1, 0) ob1 = Solution() print(ob1.solve([4, 4, 6, 4, 4]))
ইনপুট
[4, 4, 6, 4, 4]
আউটপুট
17
