题目描述

译自 ROI Regional 2025 Day2 T2. Перекошенное разбиение

给定一个由非负整数组成的数组 $[a_1, a_2, \ldots, a_n]$。

考虑将该数组划分为连续的 $k$ 个非空子段。

我们将一个划分的不平衡度定义为这些子段中最大子段和与最小子段和的差值。

你的任务是找到将该数组划分为 $k$ 个子段的最大不平衡度。

例如，如果数组为 $[2, 1, 3, 4]$：

• 划分为 $[2, 1, 3][4]$ 时，不平衡度为 $6 - 4 = 2$；
• 划分为 $[2, 1][3, 4]$ 时，不平衡度为 $7 - 3 = 4$；
• 划分为 $[2][1, 3, 4]$ 时，不平衡度为 $8 - 2 = 6$。

最后一种划分是在将数组划分为两个非空子段时的不平衡度最大值。

输入格式

第一行包含两个整数 $n$ 和 $k$ $(2 \leq k \leq n \leq 300\,000)$，分别表示数组的长度和子段的数量。

第二行包含 $n$ 个整数 $a_i$ $(0 \leq a_i \leq 10^9)$，表示数组的元素。

输出格式

输出一个整数，表示将该数组划分为 $k$ 个子段的最大不平衡度。

4 2
2 1 3 4

6

第一个样例已在题目描述中进行了详细解释。

5 4
2 1 3 4 1

6

第二个样例中，最优的划分是 $[2][1][3, 4][1]$。在这个划分中，子段的最大和为 $3 + 4 = 7$，最小和为 $1$，因此不平衡度为 $6$。

数据范围与提示

详细子任务附加限制及分值如下表所示。