分数: 300 点
问题陈述
给你一个整数序列 给出了 A=(A_1,A_2,\dots,A_N) 长度 N.
找到最大值 \displaystyle \sum_{i=1}^{M} i \times B_i 为连续子数组 B=(B_1,B_2,\dots,B_M) of A 长度 M.
注释
A 连续子数组 数列的 是通过去除 0 或更多初始条款以及 0 或原始数字序列中的更多最终项。
例如, (2, 3) 和 (1, 2, 3) 是连续的子数组 (1, 2, 3, 4),但是 (1, 3) 和 (3,2,1) 不是连续的子数组 (1, 2, 3, 4).
约束
- 1 \le M \le N \le 2 \times 10^5
- - 2 \times 10^5 \le A_i \le 2 \times 10^5
- 输入中的所有值都是整数。
输入
输入由标准输入按以下格式给出:
N M A_1 A_2 \dots A_N
输出
打印答案。
示例输入 1
4 2 5 4 -1 8
示例输出 1
15
当 B=(A_3,A_4),我们有 \displaystyle \sum_{i=1}^{M} i \times B_i = 1 \times (-1) + 2 \times 8 = 15。 既然不可能实现 16 或更大的值,解决办法是 15.
请注意,您不能选择,例如, B=(A_1,A_4).
示例输入 2
10 4 -3 1 -4 1 -5 9 -2 6 -5 3
示例输出 2
31