题目背景

• 1、请大家注意数据范围：题目虽然是 $k$ 段和，但超过一半的数据满足 $k \le 2$
• 2、我们学过 《最大 2 段和》：枚举左短，然后对右段求后缀和
• 3、现在要求 3 段和，我们枚举哪一段更好呢？
• 4、$k=3$ 的大部分数据都满足 $n <= 5000$
• 5、最后 $8$ 分请大家思考 $O(nk)$ 的做法
• 6、更巧妙的做法请参考 P6821 [PA 2012] Tanie linie

题目描述

对于给定的整数序列 $A=\lbrace a_1,a_2,…,a_n \rbrace$，找出 $k$ 个不重合连续子段，使得这 $k$ 个子段中所有数字的和最大。

输入格式

输入的第一行包含 $2$ 个正整数 $n, k$，表示 $a$ 的长度和可以选择的子段数

输入的第二行包含 $n$ 个整数表示 $a_i$

输出格式

输出一行包含一个整数，表示题目询问的答案。

9 1
-2 1 -3 4 -1 2 1 -5 4

6

10 2
1 -1 2 2 3 -3 4 -4 5 -5

13

12 3
10 -6 -3 4 -1 -8 9 6 -3 7 2 -5

35

10 2
1 -1 2 2 3 -3 4 -4 5 -5

13

提示

【样例 1 解释】

• 可以选取 $[4, -1, 2, 1], 这个子段
• 和是 $4 - 1 + 2 + 1 = 6$

【样例 2 解释】

• 可以选取 $[2, 2, 3, -3, 4], [5]$ 2 个子段
• 和是 $8 + 5 = 13$

【样例 3 解释】

• 可以选取 $[10], [4], [9, 6, -3, 7, 2]$ 3 个子段
• 和是 $10 + 4 + 21 = 35$

【数据范围】

对于所有测试数据，均有：

• $1 \le k \le 3$
• $k \le n \le 10^5$
• $-10^4 \le a_i \le 10^4$

来源