Dãy con tăng dài nhất

General
Points
30
AC Rate
0.0%
Time limit
1.0 s
Memory limit
256M
Group
graph
Submissions
Đề 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$
Draft saved