#488. DPLIQ3 – Dãy con tăng dài nhất (Bản TB)

Bộ nhớ: 256 MiB Thời gian: 1000 ms Nhập/xuất từ luồng chuẩn
Kiểu bài: Thông thường Kiểu chấm: So sánh văn bản
Đưa lên bởi: Chùm CUỐI

Đề bài

Cho một dãy số nguyên gồm N phần tử a_1, a_2, …, a_N . Một dãy con đơn điệu tăng của dãy trên là dãy a_{i_1}, a_{i_2}, …, a_{i_k} sao cho: i_1 < i_2 < … < i_k a_{i_1} < a_{i_2} < … < a_{i_k} . Hãy cho biết dãy con đơn điệu tăng của dãy đã cho có nhiều nhất bao nhiêu số hạng?

Dữ liệu vào:

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

Dữ liệu ra:

  • Ghi ra độ dài của dãy con đơn điệu tăng dài nhất.

Ví dụ:

Dữ liệu vào:
6
1 2 5 4 6 2
Dữ liệu ra:
4
Giải thích:
  • Dãy con tăng dài nhất là dãy 1, 2, 4, 6 độ dài dãy này là 4 .

Giới hạn:

  • 1 ≤ n ≤ 10^5, 1 ≤ a_i ≤ 10^6