Dãy con tăng dài nhất (bản khó)
Xem dạng PDF
Gửi bài giải
Điểm:
1,00 (OI)
Giới hạn thời gian:
2.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 30000)~
- 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
Bài này đặt giới hạn 0,3s mỗi test có vẻ không phù hợp với python