P11702 [ROIR 2025] 不平衡划分

翻译自 [ROIR 2025 D2T2](https://neerc.ifmo.ru/school/archive/2024-2025/ru-olymp-regional-2025-day2.pdf)。

给定一个非负整数数组 $[a_1, a_2, \dots, a_n]$。考虑将该数组划分成 $k$ 个非空的连续子段。我们称划分方案的“不平衡度”为这些子段和中的最大值与最小值之差。你需要求出将该数组划分成 $k$ 个子段时的最大不平衡度。 例如，如果数组为 $[2, 1, 3, 4]$，$k=2$，则： - 划分为 $[2, 1, 3][4]$ 时，不平衡度为 $6 - 4 = 2$； - 划分为 $[2, 1][3, 4]$ 时，不平衡度为 $7 - 3 = 4$； - 划分为 $[2][1, 3, 4]$ 时，不平衡度为 $8 - 2 = 6$。 其中最后一种情况的不平衡度最大。

无

无

在样例二中，最优划分方案是 $[2][1][3, 4][1]$。其中最大子段和为 $3 + 4 = 7$，最小子段和为 $1$，因此不平衡度为 $7 - 1 = 6$。 本题使用 Subtask 捆绑测试。数据中 Subtask 0 是样例。 | 子任务 | 分数 | 特殊性质 | |:---:|:---:|:---:| | $1$ | $11$ | $n \le 15$ | 第一错误 | | | $2$ | $11$ | $k = 2$ | 第一错误 | | | $3$ | $21$ | $k = 3$ | 第一错误 | | | $4$ | $15$ | $n \le 300$ | 1 | 第一错误 | | $5$ | $21$ | $n \le 3000$ | 1, 4 | 第一错误 | | $6$ |$ 21 $| 无 | 1-5 | 第一错误 |