Chương trình tìm tổng lớn nhất các phần tử không liền kề trong Python

Cho danh sách nums (có thể có số âm hoặc 0), tìm tổng lớn nhất của các phần tử không liền kề nhau.

Ví dụ: [3, 5, 7, 3, 6] → kết quả 16 (chọn 3, 7, 6).

Giải thuật (Dynamic Programming O(1) không gian)

1. Nếu : trả về .
2. Khởi tạo (tổng max không lấy phần tử trước), (tổng max lấy phần tử trước).
3. Duyệt từ 1 đến :
   • .
4. Trả về .

Ví dụ minh họa

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

Đầu vào

[3, 5, 7, 3, 6]

Đầu ra

16