#443. DPLIQ2 – Dãy con tăng dài nhất 2

Cho một dãy số nguyên gồm phần tử . Một dãy con đơn điệu tăng của dãy trên là dãy sao cho: và . Hãy tìm một dãy con tăng của dãy có nhiều phần tử nhất (dài nhât)?

Dữ liệu vào:

• Chứa số nguyên ;
• Dòng thứ hai chứa số nguyên dương , mỗi số cách nhau bởi một dấu cách.

Dữ liệu ra:

• Dòng đầu ghi ra số phần tử của dãy con tăng dài nhất của dãy
• Dòng thứ hai ghi ra một dãy con tăng dài nhất của dãy . Nếu có nhiều dãy con tăng có cùng số phần tử (nhiều nhất) thì ghi ra một dãy bất kỳ.

Ví dụ:

Dữ liệu vào:

6
1 2 5 4 6 2

Dữ liệu ra:

4
1 2 4 6

Giải thích:

• Dãy con tăng dài nhất là dãy độ dài dãy này là .

Giới hạn:

• .