Python - หาลำดับเลขคณิตยาวที่สุดที่มีความต่างคงที่

โจทย์: กำหนดรายการตัวเลข nums และค่า diff หาความยาวของลำดับเลขคณิต (Arithmetic Subsequence) ที่ยาวที่สุดซึ่งความต่างระหว่างสมาชิกติดกันเท่ากับ diff

ตัวอย่าง

Input: nums = [-1, 1, 4, 7, 2, 10], diff = 3
Output: 4
เหตุผล: ลำดับ [1, 4, 7, 10] ความต่าง = 3 ความยาว = 4

อัลกอริทึม: Dynamic Programming + Hash Map

ใช้ dp[x] = ความยาวลำดับเลขคณิตที่ลงท้ายด้วยค่า x และมีความต่าง diff

ขั้นตอนการทำงาน

1. สร้าง seen เป็น defaultdict(int) ค่าเริ่มต้น 0
2. วนลูปแต่ละ x ใน nums:
   • หาก x - diff อยู่ใน seen: seen[x] = seen[x - diff] + 1
   • มิฉะนั้น: seen[x] = 1 (เริ่มลำดับใหม่)
   • อัปเดตคำตอบสูงสุด mx = max(mx, seen[x])

โค้ด 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

# ทดสอบ
nums = [-1, 1, 4, 7, 2, 10]
diff = 3
print(solve(nums, diff))  # Output: 4

การทำงานทีละขั้นตอน (Trace)

ความซับซ้อน

• Time Complexity: O(n) - ผ่านอาร์เรย์ 1 รอบ
• Space Complexity: O(n) - Hash Map เก็บค่าที่เจอ

ข้อสังเกต

• เป็น Subsequence (ไม่ต้องติดกันในอาร์เรย์เดิม) แต่ต้องเก็บลำดับเดิม
• ใช้ defaultdict เพื่อให้ค่าเริ่มต้นเป็น 0 อัตโนมัติ
• ทำงานได้กับ diff เป็นลบด้วย (ลำดับลดลง)

การทดสอบเพิ่มเติม

print(solve([1, 2, 3, 4], 1))      # 4
print(solve([1, 3, 5, 7], 2))      # 4
print(solve([5, 3, 1, -1], -2))    # 4 (diff ลบ)
print(solve([1, 5, 9, 13], 4))     # 4
print(solve([1, 2, 4, 8], 1))      # 2 (แค่ 1,2)