Computer >> คอมพิวเตอร์ >  >> การเขียนโปรแกรม >> Python

โปรแกรมค้นหาผลรวมขององค์ประกอบที่ไม่อยู่ติดกันในรายการแบบวงกลมใน 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