Elearning CodePath – CTP Online Judge

Dãy con đều bậc K dài nhất

SEQAREK

🟢 Hard #Sliding Window #Deque

### 📌 Thông tin chung

---
### 📝 Định nghĩa Dãy con đều bậc $K$

Cho dãy số nguyên $A = (A_1, A_2, \dots, A_N)$.
Một dãy con của dãy đã cho là dãy các phần tử liên tiếp nhau $A[L..R]$.

Dãy con $A[L..R]$ được gọi là dãy con đều bậc $K$ nếu như chênh lệch giữa hai số bất kỳ trong dãy này không vượt quá $K$.

Điều kiện: $\max(A_L, \dots, A_R) - \min(A_L, \dots, A_R) \le K$.

---
### 📝 Yêu cầu

Hãy tìm dãy con đều bậc $K$ có độ dài lớn nhất.

---
### 📥 Định dạng Đầu vào

* Dòng đầu tiên ghi hai số nguyên dương $N$ (độ dài dãy) và $K$ (bậc đều).
* Dòng thứ hai ghi $N$ số nguyên $A_1, A_2, \dots, A_N$.

Giới hạn:
(Giả định giới hạn phổ biến cho bài toán này)
* $1 \le N \le 10^5$.
* $1 \le K \le 10^9$.
* $|A_i| \le 10^9$.

---
### 📤 Định dạng Đầu ra

In trên một dòng một số nguyên - kết quả tìm được (độ dài lớn nhất).

---
### ✨ Ví dụ

| Input | Output |
| :---: | :---: |
| `5 3` <br> `1 2 3 4 5` | `4` |

**Giải thích Ví dụ:**
$N=5, K=3$. Dãy: $(1, 2, 3, 4, 5)$.
* Đoạn $(1, 2, 3, 4)$: $\max=4, \min=1$. Chênh lệch $4-1=3$. $3 \le K$. Thỏa mãn. Độ dài 4.
* Đoạn $(1, 2, 3, 4, 5)$: $\max=5, \min=1$. Chênh lệch $4 > K$. Không thỏa mãn.
* Đoạn con dài nhất thỏa mãn là **4**.

---
### 🏷 Phân tích và Ràng buộc

| Subtask | Ràng buộc $N$  |  Tỷ lệ điểm |
| :--- | :--- | :--- |
| $1$ | $N \le 1000$  | $50\%$ |
| $2$ | $N \le 10^5$ | $50\%$ |

---

✅ Đã AC: 1 / 5 submissions