Gửi bài giải
Điểm:
3,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 ≤ 10^5, |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
- 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
Cho em xin code C++ đi ạ!
Đầu tiên nhập vào một số
n
.Khi nào
n > 0
.Thì nhập vào
1
sốa
.Tiếp theo dùng hàm
lower_bound()
để tìmm
là vị trí phần tử đầu tiên trong multiset có giá trị lớn hơn hoặc bằng vớia
Sau khi dùng hàm
lower_bound()
xong các bạn phải cộng thêm1
vì vị trím
trong 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ìm1
vị 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
tại sao bạn dùng multiset thay vì vector nhỉ
Bình luận này đã bị ẩn vì có quá nhiều phản ứng tiêu cực. Nhấn để xem.
dp ez
cop code mà
Bình luận này đã bị ẩn vì có quá nhiều phản ứng tiêu cực. Nhấn để xem.
eheheh
Bình luận này đã bị ẩn vì có quá nhiều phản ứng tiêu cực. Nhấn để xem.