Hints: Array Splitting

Consider any random partition and compress all elements in a segment with its sum.

$$\sum f(i)=a+2\cdot b+3\cdot c+4\cdot d+5\cdot e$$

Express $\sum f(i)$ using suffix sums. Assume $S_c$ denotes suffix sum starting from the segment containing $c$.

$$\sum f(i)=S_a+S_b+S_c+S_d+S_e$$

Hence, the cost is just the sum of $k$ elements of the suffix array. How do you maximize it?

Just sort the suffix sum array and pick the maximum $k$ elements from the suffix array. There’s a small catch.

The first suffix sum necessarily needs to be taken. The rest $k-1$ elements can be chosen freely.