पायथन में निष्कासन से अधिकतम अंक खोजने का कार्यक्रम

मान लीजिए कि हमें धनात्मक संख्याओं की एक सूची प्रदान की गई है। अब, यहां हम समान मान वाले कुछ लंबाई 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() । यह बाएँ, दाएँ, t

  . ले जाएगा

• यदि बाएँ> दाएँ गैर-शून्य है, तो

  • वापसी 0

• संख्या:=अंक [बाएं]

• लेफ्ट2 :=लेफ्ट

• जबकि बाएँ2 <दाएँ और nums[left2 + 1] अंक के समान है, करें

  • लेफ्ट2 :=लेफ्ट2 + 1

• t :=t + left2 - बाएँ + 1

• बाएँ :=बाएँ2 + 1

• अंक :=t से घात 2 + dp (बाएं, दाएं, 0)

• मध्य श्रेणी के लिए बाएँ से दाएँ + 1 करें, करें

  • अगर nums[mid], num के समान है, तो

    • अंक:=अधिकतम (अंक, डीपी (बाएं, मध्य -1, 0) + डीपी (मध्य, दाएं, टी))

• वापसी बिंदु

• मुख्य कार्य से, हम निम्नलिखित कार्य करते हैं -

• प्रिंट (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