Chương trình tìm tổng lớn nhất dãy con với hiệu giá trị bằng hiệu chỉ số

Cho danh sách số nums, chọn dãy con tăng chặt mà hiệu giữa hai số liên tiếp bằng hiệu chỉ số của chúng. Tìm tổng lớn nhất của dãy con đó.

Ví dụ: nums = [6, 7, 9, 9, 8, 5] -> chọn [6,7,9] tại chỉ số [0,1,3], hiệu giá trị [1,2] = hiệu chỉ số [1,2], tổng = 22.

Giải thuật

• Tạo dictionary d (defaultdict int).
• Duyệt enumerate(nums): với index i, value x, cập nhật d[x - i] += x.
• Trả về max của values trong d.

Ý tưởng: điều kiện x_j - x_i = j - i <=> x_j - j = x_i - i. Do đó các phần tử cùng nhóm (x - i) tạo thành dãy con thỏa mãn.

Ví dụ

class Solution:
    def solve(self, nums):
        from collections import defaultdict
        d = defaultdict(int)
        for i, x in enumerate(nums):
            d[x - i] += x
        return max(d.values())

ob1 = Solution()
nums = [6, 7, 9, 9, 8, 5]
print(ob1.solve(nums))

Đầu vào

[6, 7, 9, 9, 8, 5]

Đầu ra

22