连续部分选择问题

题目描述

翰翰 18 岁生日的时候，达达给她看了一个神奇的序列 $A_1, A_2, \dots, A_N$。

她被允许从中选择不超过 $M$ 个连续的部分作为自己的生日礼物。

翰翰想要知道选择元素之和的最大值。

你能帮助她吗？

输入格式

第一行包含两个整数 $N, M$。

第二行包含 $N$ 个整数 $A_1 \sim A_N$。

输出格式

输出一个整数，表示答案。

输入输出样例 #1

输入样例

5 2 
2 -3 2 -1 2

输出样例

5

限制条件

• $1 \le N, M \le 10^5$
• $|A_i| \le 10^4$

时间限制

1秒

空间限制

64MB

样例解释

样例 1

给定序列：$[2, -3, 2, -1, 2]$ $M = 2$（最多选择 2 个连续部分）

最优选择方案：

• 选择第 1 个部分：区间 $[1, 1]$（元素 2），和为 2
• 选择第 2 个部分：区间 $[3, 5]$（元素 2, -1, 2），和为 $2 + (-1) + 2 = 3$

总和的值为：$2 + 3 = 5$

可以验证其他选择方式都无法得到更大的和值：

• 如果只选 1 个连续部分：最大子段和为区间 $[3, 5]$ 的和 3
• 如果选 2 个连续部分：上述方案得到 5
• 无法选择超过 2 个部分（因为 $M = 2$）