Gửi bài giải
Điểm:
0,30 (OI)
Giới hạn thời gian:
1.0s
Giới hạn bộ nhớ:
256M
Input:
stdin
Output:
stdout
Dạng bài
Ngôn ngữ cho phép
C, C++, Go, Java, Kotlin, Pascal, PyPy, Python, Rust, Scratch
~Minh~ là một cậu bé khó tính. Cậu có sở thích sưu tầm những mảng số khác nhau.
Dạo gần đây, cậu ấy vừa nhặt được một mảng ~A~ gồm ~n~ số nguyên.
Minh không hài lòng với mảng ~A~ hiện tại. Cậu ấy sẽ tạo ra mảng ~B~ mới từ ~A~ bằng cách sau:
- Đầu tiên, mảng ~B~ là mảng rỗng.
- Lần lượt đi từ phần tử đầu tiên ~(A_1)~ cho đến phần tử cuối cùng ~(A_n)~. Tại lượt thứ ~i~, Minh sẽ thêm ~A_i~ vào đầu hoặc cuối của mảng ~B~.
Sau khi thực hiện thao tác trên, Minh sẽ được mảng ~B~ mới gồm ~n~ phần tử.
Minh muốn tạo mảng ~B~ sao cho độ dài của dãy con tăng ngặt tìm được trên ~B~ là lớn nhất. Hãy giúp Minh đạt được điều này.
Input
- Dòng đầu tiên chứa số nguyên ~n~ ~(1 \le n \le 10^5)~.
- Dòng tiếp theo chứa ~n~ số nguyên ~A_1, A_2, \dots, A_n~ ~(|A_i| \le 10^9)~.
Output
- Một số duy nhất là độ dài dãy con tăng ngặt dài nhất tìm được sau khi thay đổi dãy ~A~ bằng thao tác trên.
Sample Input
6
4 5 5 6 3 7
Sample Output
5
Subtask
- ~40~% số test với ~1 \le n \le 20~.
- ~30~% số test tiếp theo với ~1 \le n \le 1000~.
- ~30~% số test còn lại không có ràng buộc gì thêm.
Note
Ở test mẫu đầu tiên, lần lượt thực hiện như sau:
- Thêm số ~4~ vào mảng, mảng ~B~ trở thành ~[4]~.
- Thêm số ~5~ vào cuối mảng, mảng ~B~ trở thành ~[4, 5]~.
- Thêm số ~5~ vào cuối mảng, mảng ~B~ trở thành ~[4, 5, 5]~.
- Thêm số ~6~ vào cuối mảng, mảng ~B~ trở thành ~[4, 5, 5, 6]~.
- Thêm số ~3~ vào đầu mảng, mảng ~B~ trở thành ~[3, 4, 5, 5, 6]~.
- Thêm số ~7~ vào cuối mảng, mảng ~B~ trở thành ~[3, 4, 5, 5, 6, 7]~.
Khi đó, dãy con tăng ngặt dài nhất là ~[3, 4, 5, 6, 7]~, với độ dài là ~5~.
Bình luận
bài này thực chất là bài này: https://oj.vnoi.info/problem/beadsnb
nên trong contest có vài code chỉ cần copy code là ac thôi