पायथन में हटाने से अधिकतम अंक ज्ञात करने का प्रोग्राम

मान लीजिए हमें धनात्मक संख्याओं की एक सूची दी गई है। हम किसी भी सन्निहित सबलिस्ट को हटा सकते हैं जिसकी लंबाई t है और सभी मान समान हैं, और t*t अंक प्राप्त कर सकते हैं। हम इसे तब तक कितनी भी बार कर सकते हैं जब तक सूची खाली न हो जाए। हमें अधिकतम अंक ज्ञात करने हैं।

उदाहरण के लिए, nums = [4,4,6,4,4] के लिए आउटपुट 17 होगा (पहले 6 को हटाएं -> 1 अंक, फिर चार 4 को एक साथ हटाएं -> 16 अंक, कुल 17)।

एल्गोरिदम (DP)

• dp(left, right, t) फ़ंक्शन परिभाषित करें:
  • यदि left > right, तो 0 वापस करें
  • num = nums[left], left2 = left
  • जब left2 < right और nums[left2+1] == num: left2++
  • t += left2 - left + 1, left = left2 + 1
  • points = t**2 + dp(left, right, 0)
  • mid = left से right तक:
    • यदि nums[mid] == num: points = max(points, dp(left, mid-1, 0) + dp(mid, right, t))
  • points वापस करें
• मुख्य फ़ंक्शन से dp(0, len(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