Elearning CodePath – CTP Online Judge

Tổng Dãy Con Lớn Nhất Độ Dài Không Quá K

KSUB

🟢 Easy #Segment Tree #Fenwick Tree #Sliding Window #Deque

### 📝 Bài toán
Cho mảng số nguyên A gồm n phần tử a1, a2, ..., an và một số nguyên dương K.
Yêu cầu: Tìm một dãy con liên tiếp của mảng A có độ dài tối thiểu là 1 và tối đa là K sao cho tổng các phần tử là lớn nhất.

### 📥 Định dạng Đầu vào
Dữ liệu vào từ file KSUB.INP:
* Dòng đầu tiên chứa hai số nguyên n và K.
* Dòng thứ hai chứa n số nguyên a1, a2, ..., an.

Giới hạn:
* 1 <= K <= n <= 10^6
* |ai| <= 10^9

### 📤 Định dạng Đầu ra
Ghi ra file KSUB.OUT một số nguyên duy nhất là tổng lớn nhất tìm được.

### ✨ Ví dụ
| Input | Output |
| :--- | :--- |
| 5 2 | 11 |
| -1 5 6 -2 4 | |

Giải thích:
* K = 2, các dãy con có độ dài <= 2 là: [-1], [5], [6], [-2], [4], [-1, 5], [5, 6], [6, -2], [-2, 4].
* Tổng lớn nhất là 5 + 6 = 11.

### 🏷 Subtasks
| Subtask | Ràng buộc | Tỷ lệ điểm |
| :--- | :--- | :--- |
| 1 | n <= 2000 | 40% |
| 2 | n <= 10^6 | 60% |

✅ Đã AC: 3 / 12 submissions