分数: 400 点
问题陈述
为了成为百万富翁,M君决定通过交易下一个来赚钱 N 天。目前,他已 1000 日元,没有股票 - 他居住的国家只发行一种股票。
他因预知未来的能力而闻名全国。他已经知道下一只股票的价格 N 天数如下:
- A_1 日元上 1第一天, A_2 日元上 2- 第一天,..., A_N 日元上 N第一天。
在 i第天,M君可以进行以下交易 任意次数 (可能为零), 在他当时拥有的资金和股票数量之内.
- 购买股票:支付 A_i 日元并收到一支股票。
- 出售股票:出售一只股票 A_i 日元。
通过最优交易,M君最终能拥有的最大金额是多少?
约束
- 2 \leq N \leq 80
- 100 \leq A_i \leq 200
- 输入中的所有值都是整数。
输入
输入由标准输入按以下格式给出:
N A_1 A_2 \cdots A_N
输出
以整数形式打印出M-kun最终可以拥有的最大金额。
示例输入 1
7 100 130 130 130 115 115 150
示例输出 1
1685
在此示例输入中,M-kun 有 7 天的交易时间。一种方法是拥有 1685 日元最终如下:
- 最初,他有 1000 日元,没有库存。
- 天 1:购买 10 库存为 1000 日元。现在他有 0 日元。
- 天 2:出售 7 库存为 910 日元。现在他有 910 日元。
- 天 3:出售 3 库存为 390 日元。现在他有 1300 日元。
- 天 4:什么都不做。
- 天 5:购买 1 库存为 115 日元。现在他有 1185 日元。
- 天 6:购买 10 库存为 1150 日元。现在他有 35 日元。
- 天 7:出售 11 库存为 1650 日元。现在他有 1685 日元。
没有办法拥有 1686 日元或更多,所以答案是 1685.
示例输入 2
6 200 180 160 140 120 100
示例输出 2
1000
在此示例输入中,最好在六天内什么都不做,之后我们将得到 1000 日元。
示例输入 3
2 157 193
示例输出 3
1216
在此示例输入中,最佳购买 6 当日股票 1 并在日内出售它们 2,之后我们将有 1216 日元。