解题思路

本题是经典的“恰好选 K 段不相交连续子数组使总和最大”的动态规划问题。设：

• dp[k][i]：在前 i 个元素中恰好选 k 段、且最后一段已结束（结束位置 ≤ i）时的最大总和（也可理解为全局最优）。
• end[k][i]：在前 i 个元素中恰好选 k 段、且第 k 段必须以 i 结尾的最大总和（局部最优）。

转移：

题面描述

给定一个长度为 $N$ 的整数数组 $a_1,a_2,\dots,a_N$，请从中选择恰好 $K$ 个互不相交、非空的连续子数组，使得它们的元素和之和最大，并输出该最大和。

输入格式

• 第一行两个整数 $N, K$，分别表示数组长度与需要选择的连续子数组个数。
• 第二行包含 $N$ 个整数，表示数组元素 $a_i$。

输出格式

输出一个整数，表示选择恰好 $K$ 段后的最大总和。

数据范围

• $1 \le K \le N \le 10^3$
• $|a_i| \le 10^9$
• 结果保证在 64 位有符号整数范围内。

输入样例

5 2
1 -2 3 5 -1

输出样例

9

样例说明： 选择两段 $[1]$ 与 $[3,5]$，总和为 $1 + (3+5) = 9$。