Python - Dãy số cấp số cộng dài nhất với công sai cho trước

Cho danh sách số nums và công sai diff. Tìm độ dài dãy con (subsequence, không cần liên tiếp) dài nhất tạo thành cấp số cộng với công sai diff.

Ví dụ

Input: nums = [-1, 1, 4, 7, 2, 10], diff = 3
Output: 4
Giải thích: Dãy con [1, 4, 7, 10] có công sai 3.

Thuật toán: Quy hoạch động với Hash Map

seen[x] = độ dài dãy cấp số cộng dài nhất kết thúc bằng giá trị x.

Duyệt qua nums:

• Nếu x - diff đã gặp: seen[x] = seen[x - diff] + 1
• Ngược lại: seen[x] = 1 (bắt đầu dãy mới)
• Cập nhật max

Mã Python

from collections import defaultdict

def solve(nums, diff):
    seen = defaultdict(int)
    mx = 0
    for x in nums:
        if x - diff in seen:
            seen[x] = seen[x - diff] + 1
        else:
            seen[x] = 1
        mx = max(mx, seen[x])
    return mx

# Test
nums = [-1, 1, 4, 7, 2, 10]
diff = 3
print(solve(nums, diff))  # Output: 4

Phân tích độ phức tạp

• Thời gian: O(n) - duyệt 1 lần, tra hash map O(1)
• Không gian: O(n) - lưu hash map

Lưu ý

• Đây là bài toán subsequence (không cần liên tiếp), khác với subarray/substring (liên tiếp)
• Thứ tự duyệt nums quyết định tính hợp lệ: chỉ dùng các phần tử xuất hiện trước
• LeetCode 1218 - Longest Arithmetic Subsequence of Given Difference