LIS - Dãy con tăng dài nhất
Xem dạng PDF
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 a, hãy tìm độ lớn của dãy con tăng dài nhất của dãy này
Input
- Dòng đầu tiên chứa một số nguyên n, là độ lớn của dãy số (1 < n < ~10^6~)
- n dòng tiếp theo, mỗi dòng chứa một số nguyên của dãy a ( a < a[i] < ~10^5~)
Output
- Độ lớn của dãy con tăng dài nhất của a
Sample
Input #1
5
2
7
4
3
8
Output #1
3
Hint
- Với test trên, ta có thể nhận thấy dãy con tăng dài nhất là: [2,7,8] với độ lớn của dãy là 3
Bình luận
Đầ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
Ụ anh ơi nếu em nhập 7 và 2 3 4 5 1 6 7 thì nó in ra 6 chứ k phải 7
À em đọc nhầm đề :>
hay bạn ơi