Dãy dài nhất

Xem PDF

Điểm: 300 (p) Thời gian: 1.0s Bộ nhớ: 1G Input: bàn phím Output: màn hình

Cho dãy số nguyên \(𝐴 = (𝑎_0, 𝑎_1, … , 𝑎_{𝑛−1})\) hãy tìm một dãy con dài nhất gồm các phần tử liên tiếp trong \(𝐴\) sao cho
độ chênh lệch giữa phần tử lớn nhất và phần tử nhỏ nhất của dãy con đó không vượt quá \(\Delta\).

Input

  • Dòng 1 chứa số nguyên dương \(𝑛 \le 10^6\) và số nguyên không âm \(Δ \le 2 \times 10^9\)
  • Dòng 2 chứa \(𝑛\) số nguyên \(𝑎_0, 𝑎_1, … , 𝑎_{𝑛−1}\) cách nhau bởi dấu cách (\(∀𝑖: |𝑎_𝑖| \le 10^9\))

Output

  • Ghi ra một số nguyên duy nhất là độ dài dãy con tìm được

Example

Test 1

Input
10 6
10 5 4 3 2 1 9 8 7 6
Output
5

Bình luận

Không có bình luận nào.