分数: 333 分
问题陈述
高桥管理 N 他的花园里排列着一排花坛。花坛都有编号 1 to N 从左到右,以及花坛 i 具有定义的“美丽”值 A_i.
对于每个 N 花坛,高桥选择是否维护它。但选择养护的花坛必须满足以下条件:
- 存在一个整数 l (1 \leq l \leq N - K + 1) 使得花坛 l, l+1, \ldots, l+K-1 全部包含在维护的花坛中。
换句话说,必须存在至少一个区间,其中 K 连续的花坛全部维护完毕。只要满足这个条件,任何其他花坛都可以保留,也可以不保留。
找出选择用于维护的花坛的最大可能的美丽值总和。
约束
- 1 \leq K \leq N \leq 5 \times 10^5
- -10^9 \leq A_i \leq 10^9
- 所有输入均为整数
输入
N K A_1 A_2 \cdots A_N
- 第一行包含花坛总数 N 以及必须维护的连续花坛数量 K,用空格分隔。
- 第二行包含每个花坛的美丽值 A_1, A_2, \ldots, A_N,用空格分隔。
输出
在满足条件的情况下选择要维护的花坛时,将美丽值的最大总和打印在一行上。
示例输入 1
5 2 3 -5 4 2 -1
示例输出 1
9
示例输入 2
4 3 -2 -7 -1 -3
示例输出 2
-10
示例输入 3
10 4 5 -2 3 -1 6 -7 4 2 -3 8
示例输出 3
25
示例输入 4
20 6 4 -5 7 0 -2 9 -8 3 1 -4 6 -1 5 -7 2 8 -3 4 -6 10
示例输出 4
54
示例输入 5
1 1 -1000000000
示例输出 5
-1000000000