Bài học tiếp theo về “cấu trúc dữ liệu và giải thuật” là bài toán Longest increasing Subsequence (LIS), tức là bài toán dãy con tăng dài nhất (các phần tử tăng dần). Để hiểu rõ hơn về nó, Tuấn Anh quyết định đọc bài trước ở nhà.
Tuấn Anh tạo ra một dãy số gồm số nguyên dương và các số trong dãy nằm trong đoạn . Anh nhận ra rằng, dãy số của mình có một số dãy con tăng dài nhất, vì thế quyết định chia các vị trí ra thành các nhóm:
Không thuộc bất kì dãy con tăng dài nhất nào.
Thuộc ít nhất một dãy con tăng dài nhất nhưng không phải thuộc tất cả các dãy con tăng dài nhất.
Thuộc toàn bộ các dãy con tăng dài nhất.
Dữ liệu vào:
Dòng đầu tiên là số nguyên dương là độ dài của dãy số của Tuấn Anh;
Dòng thứ hai gồm số thể hiện dãy số.
Dữ liệu ra:
Gồm số nguyên liền nhau, số thứ có giá trị là hoặc , có nghĩa là phần tử ở vị trí thuộc vào nhóm tương ứng.
