สมมติว่าเรามีรายการตัวเลขที่เรียกว่า 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