Bài toán

Dãy con tăng dài nhất

Dãy con tăng dài nhất là một trong những bài toán QHĐ kinh điển.

Cho dãy số A có N phần tử, bài toán yêu cầu tìm dãy con dài nhất của dãy A sao cho phần tử sau của dãy con luôn lớn hơn phần tử trước. Dãy con của một dãy số là dãy có được sau khi loại bớt một số phần tử, các phần tử khác giữ nguyên vị trí.

Nói cách khác, dãy con tăng của A là một dãy (A(i_1), A(i_2),…,A(i_k)) thỏa mãn (i_1 < i_2 < … < i_k) và (A(i_1) < A(i_2) < … < A(i_k)).

Gọi (F(i)) là dãy con tăng dài nhất kết thúc ở (A(i)), ta có công thức tính:

[F(1) = 1\ F(i) = max{F(j) + 1}]

Với (j) thỏa (1 leq j < i) và (A(j) < A(i)).

Kết quả bài toán là (max{F}).

Có thể cài đặt công thức trên với độ phức tạp (O(N^2)):

Xem code dùng công thức trên để giải bài LIQ: LIQ.

Trong công thức ở trên, nếu ta gán (B(F(i))=A(i)) thì ta sẽ có mảng B với ý nghĩa: (B(k)) là giá trị kết thúc của dãy con tăng độ dài (k) (tại thời điểm đang tính).

Có thể chứng minh B là dãy tăng. Giả sử đang duyệt đến vị trí (i), đã tính được (F(i)=k). Ta gán (B(k)=A(i)) như trên, nếu có (B(k) geq B(k+1)) thì ta đã tính (F(i)) sai, vì trước (A(i)) có một phần tử (A(j) leq A(i)) mà lại có (F(j)) lớn hơn (F(i)). Tương tự cũng có thể thấy (B(k-1)>=B(k)) là điều vô lý.

Từ nhận xét B là dãy tăng, ta sử dụng tìm kiếm nhị phân để tìm dãy con tăng dài nhất trong (O(Nlog N)) như sau:

• Khởi tạo dãy B có N phần tử, (B(0) = -infty), các phần tử khác bằng (+infty).
• Duyệt (i) từ 1 đến N, mỗi lần duyệt ta tìm vị trí (k) đầu tiên có (B(k)geq A(i)) (sử dụng tìm kiếm nhị phân), gán (B(k)=A(i)) (và (F(i)=k) nếu cần).

Độ dài dãy con tăng dài nhất là vị trí (k) cuối cùng mà (B(k)neq+infty), hoặc cũng có thể lấy max trong quá trình duyệt.

Đoạn code ở dưới sử dụng hàm lower_bound để tìm (k):

Xem code dùng TKNP để giải bài LIS: LIS.

Đọc về BIT ở đây: Fenwick tree – Cây chỉ số nhị phân

Ngược với cách cải tiến bên trên, ta gán (B(A(i))=F(i)) (ở trên là (B(F(i))=A(i))). Mảng B có ý nghĩa (B(x)) là độ dài dãy con tăng dài nhất kết thúc tại phần tử có giá trị là (x).

Để tính (F(i)), ta cần tìm max từ đầu dãy (B) đến (B(A(i)-1)), sau đó gán (F(i) = max + 1) và ta cập nhật lại (B(A(i))). Sử dụng BIT để tìm max và cập nhật, độ phức tạp của thuật toán là (O(Nlog C)), với (C) là giới hạn giá trị của số trong dãy (A).

Ở đây phát sinh thêm vấn đề là các số trong dãy (A) quá lớn, ta giải quyến vấn đề này bằng cách “nén” số lại. Sau khi nén, giá trị các số chỉ từ 1 đến N và ta có thể sử dụng BIT để giải.

Xem code: Tìm dãy con chung dài nhất bằng BIT

Phương pháp nén số

Nén số tức là ta gán lại giá trị của mảng. Mảng sau khi nén có giá trị của các phần tử nhỏ hơn và vẫn giữ được quan hệ lớn bé giữ các phần tử.

Ví dụ:

Có thể xem bài viết Rời rạc hóa và ứng dụng của VNOI.

Cách làm

Cách làm cơ bản nhất là sắp xếp lại mảng, loại bỏ các phần tử bị trùng, sau đó, với mỗi phần tử (A(i)) trong mảng ban đầu, ta tìm chỉ số của phần tử đó trong mảng đã sắp xếp rồi gán lại (A(i)) bằng chỉ số đó.

Cài đặt ý tưởng

Code sau sử dụng các tiện ích trong C++ STL để nhanh chóng cài đặt ý tưởng trên:

Giải thích

2 dòng

sẽ sắp xếp lại mảng a và loại bỏ các phần tử bị trùng bằng cách chuyển a sang std::set rồi chuyển về lại std::vector. Phải chuyển về vector vì ta không thể tìm chỉ số của phần tử trong set.

Vòng for ở phía sau dùng hàm lower_bound để tìm phần tử x, sau đó trừ cho b.begin() để lấy chỉ số phần tử. Cộng thêm cho 1 vì ta muốn giá trị các phần tử bắt đầu từ 1.