Longest Increasing Subsequence trong O(n log n)

[codeaptm (Mai Đức Mạnh)]

mọi người cho e hỏi. Bài LIS có cách nào để in ra dãy con tăng lớn nhất khi làm với độ lớn n logn ko ạ?

[rogp10]

Chuyển bài toán thành tối ưu dãy tăng độ dài 1, 2, …, k rồi tìm nhị phân là O(n\log{k}). Chú ý đến tính thứ tự khi lấy kết quả

Dãy tối ưu là dãy kết thúc bằng số nhỏ nhất có thể. Số cuối của dãy thứ k sẽ nhỏ hơn số cuối của dãy thứ k+1, vì dãy thứ k+1 chứa prefix độ dài k (hay u_{k, k} \leq u_{k, k+1} < u_{k+1, k+1}) nên tìm kiếm nhị phân được. Ứng với mỗi phần tử, ta chỉ cần cập nhật một ô thôi.