Dãy con tăng dài nhất
Points
30
AC Rate
0.0%
Time limit
1.0 s
Memory limit
256M
Group
graph
Đề bài
Cho một dãy số nguyên $A$ gồm $N$ phần tử $A_1, A_2, \dots, A_N$. Một dãy con tăng ngặt là dãy thu được bằng cách xóa đi một số phần tử (có thể không xóa phần tử nào) sao cho các phần tử còn lại giữ nguyên thứ tự ban đầu và phần tử đứng sau lớn hơn hẳn phần tử đứng trước.
Hãy tìm độ dài của dãy con tăng ngặt dài nhất.
Dữ liệu vào
- Dòng đầu chứa số nguyên $N$ ($1 \le N \le 10^5$).
- Dòng thứ hai chứa $N$ số nguyên $A_1, A_2, \dots, A_N$ ($|A_i| \le 10^9$).
Dữ liệu ra
Một số nguyên duy nhất là độ dài dãy con tăng dài nhất.
Ví dụ
| Input | Output |
|---|---|
6<br>1 2 5 4 6 2 |
4 |
Giới hạn
- $1 \le N \le 10^5$
- $|A_i| \le 10^9$
Community Discussion