Cửa sổ trượtMảng
Mô tả
Ông nội bạn hay xem phim trên FPT Play bằng một chiếc Fire TV cũ. Thiết bị này hơi yếu, nên ứng dụng tải video theo từng đoạn nhỏ (chunk) rồi tạm vào bộ đệm trước khi phát. Mỗi chunk có dung lượng tính bằng MB cho trước trong một mảng. Vì RAM có hạn, ứng dụng chỉ giữ được đúng K chunk liên tiếp trong bộ đệm; khi chunk mới vào thì chunk cũ nhất bị đẩy ra. Để xem mượt nhất, bạn cần chọn đúng K chunk liên tiếp có tổng dung lượng lớn nhất, lý do là chunk càng nặng thì hình ảnh càng rõ. Hãy giúp ông nội bạn tính tổng dung lượng lớn nhất có thể đạt được bởi một cửa sổ dài đúng K chunk liên tiếp.
Đầu vào
chunks: mảng số nguyên dương, mỗi phần tử là dung lượng một chunk (MB).k: số nguyên dương, độ dài cửa sổ cần chọn.
Đầu ra
- Trả về một số nguyên dương: tổng dung lượng lớn nhất của một cửa sổ liên tiếp dài đúng
k.
Ràng buộc
- 1 ≤ k ≤ len(chunks) ≤ 10^5.
- 1 ≤ chunks[i] ≤ 10^4.
- Tổng các phần tử trong một cửa sổ không vượt quá 10^9.
Ví dụ
Giả sử chunks = [3, 1, 4, 1, 5, 9, 2, 6] và k = 3.
Các cửa sổ liên tiếp độ dài 3 là:
- [3, 1, 4] tổng 8
- [1, 4, 1] tổng 6
- [4, 1, 5] tổng 10
- [1, 5, 9] tổng 15
- [5, 9, 2] tổng 16
- [9, 2, 6] tổng 17 Tổng lớn nhất là 17, vậy kết quả trả về là 17.