Mô tả và yêu cầu

Một công ty kinh doanh tiến hành đánh giá hiệu quả làm việc của nhân viên
A (check point) dựa trên tình hình doanh thu và chi phí của họ theo thời gian trong
1 giai đoạn công tác. Một giai đoạn công tác bao gồm một chuỗi các ngày làm
việc được đánh số 1, 2, ..., N. Ngày làm việc thứ i của nhân viên A được đặc trưng
bởi 1 con số (doanh thu hoặc chi phí) ai trong đó ai > 0 có nghĩa ngày đó nhân
viên thu được lượng tiền là ai (doanh thu), ai < 0 có nghĩa nhân viên cần chi tiêu
một khoản −ai (chi phí). Hiệu quả làm việc của nhân viên A được đo bằng tổng
lợi nhuận (tổng doanh thu - tổng chi phí) lớn nhất thu được trong số các chuỗi
gồm một số liên tiếp các ngày mà trong đó có không quá K ngày nhân viên phải
chi tiêu.
Ví dụ: giai đoạn kinh doanh gồm 9 ng ày, trong đó lượng thu, chi của nhân viên
được mô tả bởi dãy gồm 9 số: 100, -1, -2, -3, 60, -4, -5, 50, -10. Việc thu chi được
thể hiện trong Bảng 1

Bảng 1: Tình hình thu và chi của nhân viên A

Yêu cầu: Cho giá trị N, K và dãy a1, ..., aN . Hãy tính hiệu quả công việc của nhân
viên A.

Dữ liệu vào

- Dòng thứ nhất chứa 2 số nguyên dương N và K (1 ≤ N ≤ 105, 0 ≤ K ≤ 100)

- Dòng thứ 2 chứa N số nguyên a1, . . . , aN

Dữ liệu ra

Ghi ra một số nguyên là hiệu quả làm việc của nhân viên A
Input Output
9 2 101
100 -1 -2 -3 60 -4 -5 50 -10