โปรแกรมหา longest subsequence ที่ความต่างสัมบูรณ์ระหว่างติดกัน ≤ K ใน Python

ได้รับลิสต์ตัวเลข nums และ k หา ความยาว subsequence ยาวที่สุด ที่ |ค่าติดกัน| ≤ k สำหรับทุกคู่ติดกันใน subsequence

ตัวอย่าง

Input: nums = [5, 6, 2, 1, -6, 0, -1], k = 4

Output: 6

แนวทางแก้ปัญหา

DP + Segment Tree (Coordinate Compression):

1. Coordinate compression: เรียงค่า unique ของ nums → mapping ค่า → index
2. Segment Tree เก็บ max length สำหรับแต่ละค่า
3. วนอ่าน nums ตามลำดับ:
   • หาช่วงค่า [x-k, x+k] ใน compressed coordinates
   • Query segment tree หา max length ในช่วงนั้น
   • Update ตำแหน่ง x ด้วย max_len + 1

การใช้งาน (Python)

import bisect
import math

class Solution:
    def solve(self, nums, k):
        # Coordinate compression
        snums = sorted(set(nums))
        n = len(snums)
        
        # Segment tree size
        size = 1
        while size < n:
            size <<= 1
        seg = [0] * (2 * size)
        
        def update(pos, val):
            pos += size
            seg[pos] = max(seg[pos], val)
            pos >>= 1
            while pos:
                seg[pos] = max(seg[pos << 1], seg[pos << 1 | 1])
                pos >>= 1
        
        def query(l, r):
            # query max in [l, r]
            l += size
            r += size + 1
            res = 0
            while l < r:
                if l & 1:
                    res = max(res, seg[l])
                    l += 1
                if r & 1:
                    r -= 1
                    res = max(res, seg[r])
                l >>= 1
                r >>= 1
            return res
        
        # Mapping value to compressed index
        idx = {v: i for i, v in enumerate(snums)}
        
        ans = 0
        for x in nums:
            lo = bisect.bisect_left(snums, x - k)
            hi = bisect.bisect_right(snums, x + k) - 1
            if lo <= hi:
                best = query(lo, hi)
            else:
                best = 0
            update(idx[x], best + 1)
            ans = max(ans, best + 1)
        
        return ans

# ทดสอบ
ob = Solution()
print(ob.solve([5, 6, 2, 1, -6, 0, -1], 4))  # Output: 6

ความซับซ้อน

• Time Complexity: O(N log N)
• Space Complexity: O(N)