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

สมมติว่าเรามีรายการตัวเลข nums เราต้องการหาผลรวมสูงสุดของตัวเลขที่ไม่ติดกัน (non-adjacent) ตัวเลขอาจเป็น 0 หรือลบก็ได้

ตัวอย่างเช่น หาก [3, 5, 7, 3, 6] ผลลัพธ์จะเป็น 16 เนื่องจากเลือก 3, 7, และ 6 ได้ 16

ขั้นตอนการแก้ปัญหา (Dynamic Programming - House Robber Pattern)

1. หาก len(nums) <= 2 ให้คืนค่า max(nums)
2. noTake = 0 (ไม่เอาตัวก่อนหน้า), take = nums[0] (เอาตัวก่อนหน้า)
3. วนลูป i จาก 1 ถึง len(nums) - 1:
   • take, noTake = noTake + nums[i], max(noTake, take)
4. คืนค่า max(noTake, take)

ตัวอย่างโค้ด Python

class Solution:
    def solve(self, nums):
        if len(nums) <= 2:
            return max(nums)
        
        noTake = 0
        take = nums[0]
        
        for i in range(1, len(nums)):
            take, noTake = noTake + nums[i], max(noTake, take)
        
        return max(noTake, take)

ob = Solution()
nums = [3, 5, 7, 3, 6]
print(ob.solve(nums))  # Output: 16

อินพุต

[3, 5, 7, 3, 6]

เอาต์พุต

16