Chương trình tìm dãy con dài nhất với chênh lệch tuyệt đối giữa phần tử liền kề ≤ k trong Python

Cho mảng nums và k. Tìm độ dài dãy con (subsequence) dài nhất sao cho hiệu tuyệt đối giữa 2 phần tử liền kề trong dãy con ≤ k.

Ví dụ: nums=[5,6,2,1,-6,0,-1], k=4 → 6.

Giải thuật (Segment Tree / Cây đoạn trên giá trị nén)

1. Nén tọa độ: sắp xếp distinct values → snums, mapping giá trị → chỉ số.
2. Cây đoạn segtree lưu độ dài dãy con dài nhất kết thúc tại giá trị đó.
3. Duyệt x trong nums theo thứ tự gốc:
   • Tìm khoảng giá trị [x-k, x+k] trên snums (binary search).
   • Query segtree max trên khoảng đó → count.
   • Update vị trí x với count+1.

Ví dụ minh họa

import math, bisect

class Solution:
    def solve(self, nums, k):
        n = 2 ** int(math.log2(len(nums) + 1) + 1)
        segtree = [0] * (2 * n)
        
        def update(i, val):
            i += n
            while i:
                segtree[i] = max(segtree[i], val)
                i //= 2
        
        def query(l, r):
            res = 0
            l += n
            r += n + 1
            while l < r:
                if l % 2:
                    res = max(res, segtree[l])
                    l += 1
                if r % 2:
                    r -= 1
                    res = max(res, segtree[r])
                l //= 2
                r //= 2
            return res
        
        snums = sorted(set(nums))
        idx = {x: i for i, x 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:
                cnt = query(lo, hi)
            else:
                cnt = 0
            update(idx[x], cnt + 1)
            ans = max(ans, cnt + 1)
        return ans

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

Đầu vào / Đầu ra

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

Output: 6