题目背景
翻译自 ROIR 2025 D2T2。
题目描述
给定一个非负整数数组 [a1,a2,…,an]。考虑将该数组划分成 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。
其中最后一种情况的不平衡度最大。
输入格式
第一行输入两个整数 n 和 k(2≤k≤n≤300000),分别表示数组的长度和需要划分的子段的数量。
第二行包含 n 个整数 a1,a2,…,an(0≤ai≤109)。
输出格式
输出一个整数,即将该数组划分为 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,因此不平衡度为 7−1=6。
本题使用 Subtask 捆绑测试。数据中 Subtask 0 是样例。
子任务 |
分数 |
特殊性质 |
1 |
11 |
n≤15 |
2 |
k=2 |
3 |
21 |
k=3 |
4 |
15 |
n≤300 |
5 |
21 |
n≤3000 |
6 |
21 |
无 |