K Segmentos de Soma Máxima
Dado um array de $N$ inteiros e um inteiro $K$, selecione no máximo $K$ subarrays contíguos não sobrepostos (cada um com comprimento $\ge 1$) para maximizar a soma total dos elementos selecionados. Você pode selecionar qualquer quantidade entre $0$ e $K$ subarrays.
Input
A primeira linha contém dois inteiros $N$ e $K$ $(1 \le K \le N \le 5 \times 10^6)$.
A segunda linha contém $N$ inteiros $a_i$ $(-10^9 \le a_i \le 10^9)$.
Output
Imprima um único inteiro: a soma máxima obtível escolhendo no máximo $K$ subarrays não sobrepostos.
8 2 1 -2 3 4 -1 2 -5 6
14
Explanation 1:
Escolher $[3, 4, -1, 2]$ (soma $8$) e $[6]$ (soma $6$) dá o total de $14$.
5 1 -3 1 -2 4 -1
4
Explanation 2:
Com $K = 1$, o problema se reduz ao clássico **subarray de soma máxima** (algoritmo de Kadane). O melhor subarray é $[4]$.
6 3 5 -1 5 -1 5 -1
15
Explanation 3:
Escolher os três subarrays de um elemento $[5]$, $[5]$, $[5]$ (nas posições 1, 3 e 5) dá soma $15$.
5 2 -5 -3 -1 -4 -2
0
Explanation 4:
Todos os elementos são negativos. A melhor estratégia é selecionar **0 subarrays**, obtendo soma $0$.