Elearning CodePath – CTP Online Judge

SlidingWindowMax

TP006

🟢 Medium #Two Pointers #Sliding Window

### 📌 Thông tin chung

---
### 📝 Định nghĩa và Yêu cầu

Cho $N$ món quà được xếp thành một hàng dài. Món quà thứ $i$ có khối lượng là $W_i$.

**Yêu cầu:** Tìm độ dài lớn nhất của một dãy quà liên tiếp $W_L, W_{L+1}, \dots, W_R$ sao cho tổng khối lượng của dãy đó $\sum_{i=L}^{R} W_i$ không vượt quá khối lượng tối đa cho phép là $K$.

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

* Dòng đầu tiên chứa hai số nguyên $N$ (số lượng quà) và $K$ (khối lượng tối đa).
* Dòng thứ hai chứa $N$ số nguyên $W_1, W_2, \dots, W_N$ (khối lượng của mỗi món quà).

Giới hạn:
(Phần giới hạn bị thiếu trong đề bài gốc, ta giả định giới hạn dựa trên tính chất bài toán và subtask)
* Giả định $N \le 10^5$.
* Giả định $W_i \ge 0$ (khối lượng không âm).

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

In ra một số nguyên duy nhất là độ dài của dãy quà liên tiếp dài nhất có tổng khối lượng không vượt quá $K$.

---
### ✨ Ví dụ

| SlidingWindowMax.inp | SlidingWindowMax.out |
| :---: | :---: |
| `7 15` <br> `2 1 5 8 4 3 6` | `3` |

**Giải thích Ví dụ:**
$N=7, K=15$. Dãy khối lượng: $(2, 1, 5, 8, 4, 3, 6)$.
Các đoạn liên tiếp có tổng $\le 15$:
* $(2, 1, 5, 8)$: Tổng $16 > 15$. Loại.
* $(1, 5, 8, 4)$: Tổng $18 > 15$. Loại.
* $(2, 1, 5)$: Tổng $8 \le 15$. Độ dài $3$.
* $(5, 8, 4)$: Tổng $17 > 15$. Loại.
* $(8, 4, 3)$: Tổng $15 \le 15$. Độ dài $3$.
* Đoạn dài nhất là $(2, 1, 5)$ hoặc $(8, 4, 3)$, có độ dài là **3**.

---
### 🏷 Ràng buộc

| Subtask | Giới hạn $N$ | Tỷ lệ điểm |
| :--- | :--- | :--- | 
| $1$ | $N \le 1000$ | $30\%$ |
| $2$ | $N \le 10^5$ | $70\%$ |

---

✅ Đã AC: 7 / 14 submissions