Which algorithms can help to solve this?

Question

Sum of minima
Mike has a notepad with N pages numerated from 1 to n. On the i page there is an Ai integer number.
Ann's going to rip off the nodepad on K parts. Then Mike will find the minimal number in each of K parts and sum them all up. Ann wants this sum to be as big as possible. Help her to rip off the nodepad to maximize the sum of minimal values.

Input Form
First line contains two numbers: N, K (2<=K<=N<=300).
Second line contains N integer numbers: A1, A2, ..., An (1<=Ai<=10^9).

Output Form
On the first line write maximal sum which Ann can reach
On the second line write the last positions of each of K parts. If there is several variants of ripping off the nodepad, write any of them.

Input sample:
10 5
1 10 2 8 9 3 5 4 7 6
Output sample:
27
3 4 5 8
Explanation:
Ann ripped off the nodepad on parts [1, 10, 2], [8], [9], [3, 5, 4], [7, 6]
The sum: 1+8+9+3+6=27

Answer 1

https://code.sololearn.com/ccfbpQnDbk6L/?ref=app

Answer 2

recursion

Answer 3

Talk to me :(

Answer 4

My hero!