Giới Thiệu

LIS là một bài toán tìm một dãy con trong một tập các phân tử, mà các phần tử trong dãy con được sắp xếp theo thứ tự (nhỏ đến lớn) mà dãy con này dài nhất có thể. Dãy con này không cần thiết phải liền kề, hoặc là duy nhất. Bài toán dãy con tăng dài nhất được áp dụng rộng rãi ở nhiều lĩnh vực: Toán học (thuật toán, lý thuyết ma trận, lý thuyết đại diện) hay Vật Lý. Thuật toán LIS giải trong độ phức tạp O(n*logn) với "n" là độ dài của dãy phần tử cho trước.

Ví dụ

Một dãy cho trước như sau

0, 8, 4, 12, 2, 10, 6, 14, 1, 9, 5, 13, 3, 11, 7, 15

Dãy con tăng dài nhất trong chuỗi số trên có độ dài 6 phần tử

0, 2, 6, 9, 11, 15

Nhưng dễ dàng thấy rằng, dãy này không phải là duy nhất, ngoài ra còn những dãy khác cũng thỏa mãn là dãy con tăng dài nhất

0, 4, 6, 9, 11, 15 hoặc 0, 4, 6, 9, 13, 15

Thuật toán

Thuật toán của bài toán LIS này được giải quyết hiệu quả với độ phức tạp O(N*logN) qua việc sự dụng mảng và tìm kiếm nhị phân. Thuật toán xét lần lượt các phần tử, duy trì LIS đã tìm được tính tới thời điểm đang xét.

Giả sử kí hiệu các tập con là A[0] , A[1] , ... thì sau khi xử lý tập A[i], thuật toán sẽ lưu lại 2 mảng:

• M[j] : lưu số (thứ tự) "k" của tập A mà dãy con đó thỏa mãn tính chất và có độ dài j, với:
  • j là độ dài của dãy con tăng dài nhất tính tới thời điểm i
  • k là phần tử cuối của dãy con tăng tính tới thời điểm i
• P[k] : lưu số (thứ tự) đằng trước số k trong dãy con tăng dài nhất (mà kết thúc là số k)

Ngoài ra ta có thể lưu thêm một biến L là độ dài của dãy con tăng dài nhất mà ta đã tìm được

Lưu ý rằng, tại mọi thời điểm trong khi xét, dãy A[M[0]] , A[M[1]] ,... A[M[L]] là một dãy không giảm. Nếu có một dãy con tăng có độ dài i (kết thúc tại A[M[i]]) thì cũng có một dãy con tăng khác độ dài i-1 (kết thúc tại A[P[M[i]]])

Pseudo Code

mảng P : dãy có độ dài N
mảng M : dãy có độ dài N+1
biến L = 0

for i = 0 -> N-1:
    //Chặt nhị phân để tìm số j lớn nhất sao cho j ≤ L mà A[M[j]] < A[i]
    đầu = 1
    cuối = L
    while đầu ≤ cuối:
        giữa = giá trị nguyên của (đầu + cuối) / 2
        if A[M[giữa]] < A[i]:
            đầu = giữa + 1
        else:
            cuối = giữa - 1
        endif
    endwhile

    //Sau khi chặt nhị phân, "đầu" lớn hơn so với độ dài của dãy liền trước A[i]
    Lmới = đầu

    //Gán giá trị liền trước của dãy bằng số Lmới-1
    P[i] = M[Lmới-1]
    M[Lmới] = i;

    if Lmới > L:
        L = Lmới //do ta đã tìm được dãy con tăng có độ dài dài hơn dãy con tăng cũ
    endif
endfor

// Dựng lại dãy con tăng
mảng S : độ dài L
k = M[L]
for i = L-1 -> 0:
    S[i] = A[k]
    k = P[k]
endfor

Nguồn: Wikipedia