Dãy con dài nhất
Xem dạng PDF
Gửi bài giải
Điểm:
100,00 (OI)
Giới hạn thời gian:
1.0s
Giới hạn bộ nhớ:
256M
Input:
stdin
Output:
stdout
Tác giả:
Dạng bài
Ngôn ngữ cho phép
C++, Python
Dãy con dài nhất
Mô tả và yêu cầu
Dãy con dài nhất
Tên file chương trình DAYCON.*
Cho một dãy gồm 𝑛 số nguyên dương, các số được đánh số thứ tự từ 1 đến 𝑛, số thứ 𝑖
có giá trị là 𝑎𝑖.
Hãy lập trình xác định độ dài một dãy con gồm các phần tử liên tục dài nhất của dãy số
đã cho sao cho độ chênh lệch giữa hai phần tử đứng kề nhau trong dãy con này không vượt
quá 𝑥.
Dữ liệu vào: cho trong file văn bản DAYCON.INP có cấu trúc như sau:
Dòng đầu ghi hai số nguyên dương 𝑛, 𝑥 (𝑛, 𝑥 ≤ 105).
Dòng thứ hai ghi 𝑛 số nguyên dương, số thứ 𝑖 cho biết giá trị 𝑎𝑖 (𝑎𝑖 ≤ 106).
Kết quả: ghi ra file văn bản DAYCON.OUT một số là kết quả tìm được.
Ví dụ
DAYCON.INP DAYCON.OUT
6 2 4
2 3 6 4 3 5
Lưu ý: có 80% số test có 𝑛 ≤ 102.
Bình luận