DCTDN1 - 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
Tác giả:
Dạng bài
Ngôn ngữ cho phép
C, C#, C++, Go, Java, Pascal, Perl, PHP, Python, Ruby, Rust, Scratch, Swift
Cho một dãy số nguyên gồm ~N~ phần tử ~a_1, a_2, …, a_N~. Một dãy con đơn điệu tăng của dãy trên là dãy ~a_{i_1}, a_{i_2}, …, a_{i_k}~ sao cho: ~i_1 < i_2 < … < i_k~ và ~a_{i_1} < a_{i_2} < … < a_{i_k}~. Hãy cho biết dãy con đơn điệu tăng của dãy đã cho có nhiều nhất bao nhiêu số hạng?
Input
- Dòng đầu chứa số nguyên dương ~N~;
- Dòng thứ hai chứa ~N~ số nguyên dương ~a_1, a_2, …, a_N~, mỗi số cách nhau bởi một dấu cách.
Giới hạn:
- ~1 ≤ n ≤ 1000, -10^9 ≤ a_i ≤ 10^9~
Output
- Ghi ra độ dài của dãy con đơn điệu tăng dài nhất.
Sample
Input #1
6
1 2 5 4 6 2
Output #1
4
Hint
Giải thích #1:
- Dãy con tăng dài nhất là dãy ~1, 2, 4, 6~ độ dài dãy này là ~4~.
Problem source: Chuyên Sơn La Online Judge
Bình luận
day so: 1 2 5 4 5 6 Vi tri: 0 1 2 3 4 5 day so khi sort: 1 2 4 5 5 6 Vi tri khi sort: 0 1 3 2 4 5 taa thay khi sort a[i1]<a[i2] nhung vi tri lai nguoc lai vi vay ta se dem xoi
Đầu tiên nhập vào một số
n.Khi nào
n > 0.Thì nhập vào
1sốa.Tiếp theo dùng hàm
lower_bound()để tìmmlà vị trí phần tử đầu tiên trong multiset có giá trị lớn hơn hoặc bằng vớiaSau khi dùng hàm
lower_bound()xong các bạn phải cộng thêm1vì vị trímtrong multiset thực tế làm+1.Rồi kiểm tra xem nều
m != multiset.end()thì xoámđi.(Nếu như
m != multiset.end()thì xoá đi để tìm1vị trí khác thoả mãn)Thì kích thước của multiset sẽ là kết quả của bài.
Code mẫu (C++) tại Đây
test 6 la jz mng;-;??
ví dụ 5 1 7 3 4 8 thì chuỗi con dài nhất phải là 4(1,3,4,8), mà code của bạn ra 3(1,7,8)