Em đang làm bài LIS (nguồn: http://vn.spoj.com/problems/LIS/).
Em có nghiên cứu lời giải của 1 bạn: http://ideone.com/J7ipfR#comments. Bạn đó có thêm lời giải thích: Dùng thuật toán tìm kiếm nhị phân (Binary Search), với F[i] là vị trí của số hạng nhỏ nhất của các dãy con tăng có độ dài là i. Tại mỗi bước, nếu A[i] lớn hơn phần tử lớn nhất trong dãy con tăng dài nhất hiện thời thì bổ sung A[i] vào cuối dãy, nếu không thì dùng hàm Search (hàm tìm kiếm nhị phân) tìm kiếm vị trí thích hợp để đặt A[i] vào nhằm đảm bảo rằng tại mỗi vị trí i sẽ có một phần tử nhỏ nhất là đuôi của dãy con tăng có độ dài i.
Nhưng em không hiểu ở trên bạn nói là F[i] là vị trí của số hạng nhỏ nhất của dãy con tăng có độ dài i, ở dưới thì nói là so sánh A[i] với phần tử lớn nhất trong dãy con tăng dài nhất (trong code là so sánh A[i] với A[F[res]]. Vậy cuối cùng ý nghĩa của dãy F là gì?
Em mong nhận được sự giúp đỡ.
Em xin cảm ơn.