Mô tả
Tại trung tâm dữ liệu AI của Viettel, kỹ sư Huyền đang phụ trách quản lý các lô dữ liệu huấn luyện mô hình. Mỗi lô dữ liệu được gắn một mã ưu tiên là số nguyên dương, và các lô được sắp sẵn theo thứ tự thời gian nhận vào kho. Đểpipeline huấn luyện chạy trơn tru, Huyền cần chọn ra một chuỗi các lô từ kho sao cho: thứ tự thời gian không thay đổi và mã ưu tiên tăng dần nghiêm ngặt. Chuỗi như vậy gọi là một dãy con tăng.
Ví dụ, với dãy mã [3, 1, 4, 1, 5, 9, 2, 6], Huyền có thể chọn các lô mang mã 1, 4, 5, 9 — bốn lô này vừa giữ đúng thứ tự thời gian vừa có mã tăng dần. Nhiệm vụ của bạn là giúp Huyền tìm chiều dài lớn nhất của một dãy con tăng như vậy.
Đầu vào
- Dòng đầu chứa một số nguyên
n(1 ≤ n ≤ 10^4) — số lượng lô dữ liệu. - Dòng thứ hai chứa
nsố nguyêna_1, a_2, ..., a_n(1 ≤ a_i ≤ 10^9), cách nhau bởi dấu cách — mã ưu tiên của từng lô theo thứ tự thời gian.
Đầu ra
- In ra một số nguyên duy nhất: chiều dài của dãy con tăng dài nhất.
Ràng buộc
- 1 ≤ n ≤ 10^4
- 1 ≤ |a_i| ≤ 10^9
- Thời gian: 2 giây cho mỗi test.
Ví dụ
Ví dụ 1:
Input:
8 3 1 4 1 5 9 2 6
Output:
4
Giải thích: Dãy ban đầu là [3, 1, 4, 1, 5, 9, 2, 6]. Một dãy con tăng dài nhất là 1, 4, 5, 9 (lấy phần tử ở các vị trí thứ 2, 3, 5, 6). Bạn có thể kiểm tra: không tồn tại dãy con tăng nào dài hơn 4. Ví dụ 1, 4, 5, 6 cũng là một đáp án hợp lệ khác.