Split Largest Sum - Classic Problems | Repovive

CLS57. Split Largest Sum

2s256 MB

Split an array into at most $k$ non-empty consecutive parts. Minimize the largest part sum.

\begin{array}{l} n \quad k \\ a_1 \quad a_2 \quad \ldots \quad a_n \end{array}

sum_{\min}

Input

5 2
7 2 5 10 8

Explanation

Splitting as 7 2 5 and 10 8 makes the largest part sum 18, which is optimal.

Output

Input

4 4
1 2 3 4

Explanation

Each element can be its own part, so the largest part sum is the maximum element, 4.

Output

Input

6 3
5 1 2 7 3 4

Explanation

One optimal split is 5 1 2, 7, and 3 4, giving largest sum 8.

Output

Split an array into at most $k$ non-empty consecutive parts. Minimize the largest part sum.

\begin{array}{l} n \quad k \\ a_1 \quad a_2 \quad \ldots \quad a_n \end{array}

sum_{\min}