Elearning CodePath – CTP Online Judge

Tổng Đoạn Con Độ Dài Bị Chặn Tối Đa

TP004

🟢 Hard #General #Tree #Two Pointers #Array

### 📌 Thông tin chung

---
### 📝 Bài toán

Cho dãy số nguyên $A = (a_1, a_2, \dots, a_n)$, và hai số nguyên dương $L, R$.

Ta gọi dãy con là một dãy gồm các phần tử liên tiếp: $A[i..j] = (a_{i}, a_{i+1}, \dots, a_{j})$ với $1 \le i \le j \le N$.

* **Độ dài** của dãy con là $j - i + 1$.
* **Trọng số** của dãy con là tổng các phần tử của nó: $S(i, j) = \sum_{k=i}^{j} a_k$.

Một dãy con được gọi là **có độ dài bị chặn** nếu:
$$
L \le j - i + 1 \le R
$$

Yêu cầu: Tìm **trọng số lớn nhất** (tổng tối đa) của dãy con có độ dài bị chặn.
$$
\text{Max Sum} = \max \{ S(i, j) \mid 1 \le i \le j \le N, L \le j - i + 1 \le R \}
$$

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

* Dòng đầu tiên: Ba số nguyên dương $N, L, R$.
* Dòng tiếp theo: $N$ số nguyên $a_1, a_2, \dots, a_n$.

Giới hạn: $1 \le N \le 10^6$, $1 \le L \le R \le N$.

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

Ghi ra file `SUM2.OUT` một số nguyên duy nhất là tổng lớn nhất tìm được.

---
### 🏷 Phân Subtask

| Subtask | Ràng buộc | Số điểm ước tính | 
| :--- | :--- | :--- |
| 1 | $N \le 10^3$ | $50\%$ |
| 2 | $N \le 10^6$ | $50\%$ |

✅ Đã AC: 2 / 6 submissions