โปรแกรมหาผลรวมองค์ประกอบไม่ติดกันใน circular list ใน Python

สมมติว่ามีรายการตัวเลข nums แทน circular list ต้องการหาผลรวมมากสุดของตัวเลขที่ไม่ติดกัน

ตัวอย่าง: nums = [10, 3, 4, 8] ผลลัพธ์ 14 เลือก 10 และ 4 (ไม่สามารถเลือก 10 และ 8 ได้เพราะติดกันแบบ circular)

ขั้นตอนการแก้ปัญหา

1. n = len(nums)
2. nums1 = nums[:n-1] (ไม่รวมตัวสุดท้าย), nums2 = nums[1:] (ไม่รวมตัวแรก)
3. ฟังก์ชัน f(i) สำหรับ nums1: คืน max(nums1[i] + f(i+2), f(i+1))
4. ฟังก์ชัน g(j) สำหรับ nums2: คืน max(nums2[j] + g(j+2), g(j+1))
5. คืน max(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