Thuật toán Left - right

Thuật toán Left - right

Bài toán: Cho một dãy A[1..n], với mỗi A[i], tìm L[i], R[i] dài nhất về 2 bên sao cho A[i] là min A[L[i]..R[i]]. Tìm thuật toán xây dựng L[i], R[i] trong O(n)

Trước hết mình sẽ nói tìm L, tìm R hoàn toàn tương tự
Khởi tạo L[i]=i, ta sẽ tìm L[i] vs i=1...n
Ta có nhận xét sau:
Nếu A[L[i]-1]>=A[L[i]] thì rõ ràng là đoạn L[i]-1..i phủ được đoạn L[i]..i vì đoạn A[L[i]..i]>=A[i] rồi, giờ có thêm 1 cái A[L[i]-1]>=A[i] nữa thì vẫn đảm bảo!!
Mà A[L[i]-1] lại là min của đoạn A[L[L[i]-1]..L[i]-1] nên nó cứ tiếp tục nhảy cóc như thế..

//Code:
for i:=1 to N do
begin
L[i]:=i;k:=i-1;
while (k>0) and (A[i]<=A[k]) do
begin
L[i]:=L[k];
k:=L[k]-1;
end;
end;

Tìm R thì chỉ for cuối về đầu, k=i+1 vs k=R[k]+1 thôi!!

áp dụng Kagain, QBSquare , ...