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

Giới hạn

• Thời gian: 0.73s
• Bộ nhớ: 1536MB
• Mã nguồn: 20000 bytes

Ghi chú: Các bài VNOI đã được chuyển qua VNOJ (Thông báo). Đề bài trên VNOI và vn.spoj.com sẽ không được cập nhật nữa. Một số đề bài không chính xác sẽ chỉ được cập nhật trên VNOJ. Bạn vẫn có thể tìm kiếm đề bài trên VNOI.

Link đọc đề trên VNOJ

Cho một dãy số nguyên gồm N phần tử A[1], A[2], ... A[N].
Biết rằng dãy con tăng đơn điệu là 1 dãy A[i ₁ ],... A[i _k ] thỏa mãn
i ₁ < i ₂ < ... < i _k và A[i ₁ ] < A[i ₂ ] < .. < A[i _k ]. Hãy cho biết dãy con tăng đơn điệu dài nhất của dãy này có bao nhiêu phần tử?

Download test và solution (C/C++, Pascal) tại đây .

Input

• Dòng 1 gồm 1 số nguyên là số N (1 ≤ N ≤ 1000).
• Dòng thứ 2 ghi N số nguyên A[1], A[2], .. A[N] (1 ≤ A[i] ≤ 10000).

Output

Ghi ra độ dài của dãy con tăng đơn điệu dài nhất.

Ví dụ

Input:
6
1 2 5 4 6 2 

Output:
4

Giải thích test ví dụ: Dãy con dài nhất là dãy A[1] = 1 < A[2] = 2 < A[4] = 4 < A[5] = 6, độ dài dãy này là 4.

Gợi ý: Sử dụng phương pháp Quy Hoạch Động. F[i]: Độ dài dãy con đơn điệu tăng dài nhất mà phần tử cuối cùng là số A[i] này.

---

• Người up: hard7771988
• Nguồn bài: Dân gian