Hints: Array Splitting graph LR A[a] --- B[b] --- C[c] --- D[d] --- E[e] Hint 1 ↕ 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$. Answer to Hint 1 | Hint 2 ↕ $$\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? Answer to Hint 2 ↕ Just sort the suffix sum array and pick the maximum $k$ elements from the suffix array. There’s a small catch. Final Hint ↕ The first suffix sum necessarily needs to be taken. The rest $k - 1$ elements can be chosen freely.
