分数: 400 点
问题陈述
给你一个整数序列 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) 长度 M of A.
注释
A 子序列 是通过去除 0 或原始数字序列中的多个元素,并在不更改顺序的情况下连接剩余元素。
例如, (10,30) 是以下序列的子序列 (10,20,30),但是 (20,10) 不是以下的子序列 (10,20,30).
约束
- 1 \le M \le N \le 2000
- - 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
21
当 B=(A_1,A_4),我们有 \displaystyle \sum_{i=1}^{M} i \times B_i = 1 \times 5 + 2 \times 8 = 21。 既然不可能实现 22 或更大的值,解决办法是 21.
示例输入 2
10 4 -3 1 -4 1 -5 9 -2 6 -5 3
示例输出 2
54