P6821 [PA 2012] Cheap Lines

PA 2012 R5.

Given a sequence containing $n$ numbers, find the maximum possible sum of at most $k$ non-overlapping subarrays.

The first line contains two positive integers $n, k$. The next line contains $n$ integers, which form the sequence.

Output one integer, the answer.

For $100\%$ of the testdata, $1 \le k \le n \le 10^6$. All numbers in the sequence are within $[-10^9, 10^9]$. Translated by ChatGPT 5