P2389 Downsizing in the Computer Class

The neighboring new Grade 7 computer class just finished an exam, and it is BlingBling’s downsizing time again. The teacher assigned this task to ZZY, but since ZZY is busy solving problems, he passed this important task onto you.

ZZY has a unique downsizing method: each student has an exam score $a_i$ ($-1000 \le a_i \le 1000$). Among $n$ students ($n \le 500$), choose no more than $k$ ($k \le n$) contiguous segments of students to keep, and dismiss the unselected students, so that the sum of the remaining students’ scores is maximized. Note that wrong answers deduct points [don’t ask me why], so scores may be negative.

The first line contains $n, k$. The second line contains the scores of students $1$ to $n$.

A single number $s$, the maximum sum of scores.

2014 Peng Kunzhi: "The statement is so short — looks trivial at first glance." Translated by ChatGPT 5