โปรแกรมค้นหาผลรวมขององค์ประกอบที่ไม่อยู่ติดกันในรายการแบบวงกลมใน python

สมมติว่าเรามีรายการตัวเลขที่เรียกว่า nums ซึ่งเป็นตัวแทนของรายการแบบวงกลม เราต้องหาผลรวมของจำนวนที่ไม่ติดกันมากที่สุด

ดังนั้น หากอินพุตเป็น nums =[10, 3, 4, 8] ผลลัพธ์จะเป็น 14 เนื่องจากเราสามารถหา 10 และ 4 ได้ เรารับ 10 และ 8 ไม่ได้เนื่องจากอยู่ติดกัน

เพื่อแก้ปัญหานี้ เราจะทำตามขั้นตอนเหล่านี้ -

• n :=ขนาดของ nums
• nums1 :=nums[จากดัชนี 0 ถึง n - 2]
• nums2 :=nums[จากดัชนี 1 ถึงปลาย]
• กำหนดฟังก์ชัน f() นี่จะใช้เวลาฉัน
• ถ้า i>=ขนาดของ nums1 แล้ว
  • คืน 0
• คืนค่าสูงสุดของ nums1[i] + f(i + 2) และ f(i + 1)
• กำหนดฟังก์ชัน g() นี่จะใช้เวลา j
• ถ้า j>=ขนาดของ nums2 แล้ว
  • คืน 0
• คืนค่าสูงสุดของ nums2[j] + g(j + 2) และ g(j + 1)
• จากวิธีหลัก ให้ทำดังนี้ -
• ผลตอบแทนสูงสุด f(0) และ g(0)

ให้เราดูการใช้งานต่อไปนี้เพื่อความเข้าใจที่ดีขึ้น -

ตัวอย่าง

class Solution:
   def solve(self, nums):
      n = len(nums)
      nums1 = nums[: n - 1]
      nums2 = nums[1:]
      def f(i):
         if i >= len(nums1):
            return 0
         return max(nums1[i] + f(i + 2), f(i + 1))
      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