Dãy con tăng dài nhất (bản dễ)

Xem dạng PDF

Gửi bài giải

Điểm: 1,00 (OI)
Giới hạn thời gian: 1.0s
Giới hạn bộ nhớ: 256M
Input: stdin
Output: stdout

Tác giả:
Dạng bài

Cho một dãy số nguyên gồm ~N~ phần tử ~X_1, X_2, ..., X_N~.

Biết rằng dãy con tăng đơn điệu là dãy ~X_{i_1}, X_{i_2}, ..., X_{i_k}~ thỏa mãn điều kiện ~i_1 < i_2 < ... < i_k~ và ~X_{i_1} < X_{i_2} < ... < X_{i_k}~. Hãy cho biết dãy con tăng đơn điệu dài nhất có bao nhiêu phần tử?

Input

  • Dòng đầu tiên gồm 1 số nguyên dương ~N (1 \leq N \leq 1000)~
  • Dòng thứ 2 gồm ~N~ số nguyên ~X_1, X_2, ..., X_N (1 \leq X_i \leq 10000)~

Output

  • Ghi ra số nguyên là độ dài của dãy con tăng đơn điệu dài nhất

Sample input

5
1 3 2 6 8

Sample output

4

Note

Dãy con tăng đơn điệu dài nhất là dãy ~X_1 = 1 < X_2 = 3 < X_4 = 6 < X_5 = 8~, độ dài dãy này bằng 4


Bình luận

Hãy đọc nội quy trước khi bình luận.


Không có bình luận tại thời điểm này.