Tóm tắt đề bài: cho một dãy A, hãy tìm đoạn con (không liên tiếp) mà các phần tử liền kề nhau có độ chênh lệch không vượt quá K.
N <= 50000
K <= 10^6
Vd:
N = 8, K = 2
4 10 9 3 8 4 7 9
OUPUT: 5
Đoạn con là [10, 9, 8, 7, 9]
Bài này em giải được bằng cách quy hoạch động, đpt O(N.K) nhưng mà với độ phức tạp như vậy sẽ bị TLE, có thuật toán nào tối ưu hơn không ạ ?
bài này chắc O(n^2), tham khảo huyền hoại quy hoạch động “dãy con tăng dài nhất”, chỉ khác nhau công thức truy hồi, chỉ khác nhau ở điều kiện,
với j > i thì a[j] > a[j]
bài này đổi thành diff(a[j], a[i]) <= k
Bài này build một cái segment tree S rồi query và cập nhật S_{a_i} = max([S_{a_i-k},S_{a_i+k}]) thì chắc độ phức tạp sẽ còn O(NlogK) ?
83% thành viên diễn đàn không hỏi bài tập, còn bạn thì sao?