পাইথনে অপসারণ থেকে সর্বাধিক পয়েন্ট খুঁজে বের করার জন্য প্রোগ্রাম

ধরুন আমাদের ইতিবাচক সংখ্যার একটি তালিকা দেওয়া হয়েছে। এখন, এখানে আমরা একই মানের সাথে কিছু দৈর্ঘ্যের t-এর যেকোনো সংলগ্ন উপ তালিকা সরিয়ে ফেলতে পারি এবং পয়েন্ট t * t পেতে পারি। একটি শর্ত বিবেচনা করা হয়, যে তালিকাটি খালি না হওয়া পর্যন্ত আমরা এটি যে কোনও সংখ্যক বার সম্পাদন করতে পারি। তাই আমরা সর্বোচ্চ কত পয়েন্ট পেতে পারি তা নির্ধারণ করতে হবে।

সুতরাং, ইনপুট যদি সংখ্যার মত হয় =[4, 4, 6, 4, 4], তাহলে আউটপুট হবে 17।

আউটপুটের জন্য, আমরা প্রথমে 6টি মুছে ফেলতে পারি যার দৈর্ঘ্য 1 আছে এবং 1 * 1 =1 পয়েন্ট পাওয়া যায়। তারপর আমরা তালিকাটি নিতে পারি [4, 4, 4, 4] যার দৈর্ঘ্য 4 এবং ফলন 4 * 4 =16 পয়েন্ট। সুতরাং অবশেষে, আমরা 17 পয়েন্ট পেতে পারি।

এটি সমাধান করতে, আমরা এই পদক্ষেপগুলি অনুসরণ করব -

• একটি ফাংশন dp() সংজ্ঞায়িত করুন। এটি বাম, ডান, টি

  লাগবে

• যদি বাম> ডান অ-শূন্য হয়, তাহলে

  • রিটার্ন 0

• সংখ্যা :=সংখ্যা[বাম]

• left2 :=left

• যখন left2

  • left2 :=left2 + 1

• t :=t + left2 − left + 1

• left :=left2 + 1

• পয়েন্ট :=t থেকে পাওয়ার 2 + dp(বাম, ডান, 0)

• মাঝামাঝি ব্যাপ্তির জন্য বাম থেকে ডান + 1, করুন

  • যদি nums[mid] num এর মত হয়, তাহলে

    • পয়েন্ট :=সর্বাধিক (পয়েন্ট, dp(বাম, মধ্য − 1, 0) + dp(মধ্য, ডান, টি))

• রিটার্ন পয়েন্ট

• প্রধান ফাংশন থেকে, আমরা নিম্নলিখিতগুলি করি -

• মুদ্রণ(dp(0, সংখ্যার আকার − 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