पायथन में सर्कुलर लिस्ट में नॉन-एडजेसेंट तत्वों का योग खोजने का प्रोग्राम

मान लीजिए हमारे पास nums नामक संख्याओं की एक सूची है जो एक सर्कुलर लिस्ट को दर्शाती है। हमें नॉन-एडजेसेंट संख्याओं का सबसे बड़ा योग ढूंढना है।

उदाहरण के लिए, यदि इनपुट nums = [10, 3, 4, 8] है, तो आउटपुट 14 होगा, क्योंकि हम 10 और 4 ले सकते हैं। हम 10 और 8 नहीं ले सकते क्योंकि वे सन्निहित हैं।

समाधान दृष्टिकोण

इसे हल करने के लिए हम निम्नलिखित चरणों का पालन करेंगे (हाउस रॉबर II - दो केस):

• n := len(nums)
• nums1 := nums[0:n-1] (पहला तत्व शामिल, अंतिम बाहर)
• nums2 := nums[1:] (पहला बाहर, अंतिम शामिल)
• फंक्शन f(i) परिभाषित करें nums1 के लिए (रिकर्सिव + मेमो):
  • यदि i >= len(nums1): 0 लौटाएं
  • max(nums1[i] + f(i+2), f(i+1)) लौटाएं
• फंक्शन g(j) परिभाषित करें nums2 के लिए
• max(f(0), g(0)) लौटाएं

उदाहरण कोड

class Solution:
    def solve(self, nums):
        n = len(nums)
        nums1 = nums[:n-1]
        nums2 = nums[1:]
        from functools import lru_cache
        @lru_cache(None)
        def f(i):
            if i >= len(nums1):
                return 0
            return max(nums1[i] + f(i+2), f(i+1))
        @lru_cache(None)
        def g(j):
            if j >= len(nums2):
                return 0
            return max(nums2[j] + g(j+2), g(j+1))
        return max(f(0), g(0))

ob = Solution()
nums = [10, 3, 4, 8]
print(ob.solve(nums))

इनपुट

[10, 3, 4, 8]

आउटपुट

14