c098. 寶石 - TCFSH CIRC Judge

Content

有 $n$ 個數字，分別代表寶石的售價，如果你在 $i$ 時間點買入/賣出的話，那你會付出/得到 $a_i$ 個金幣
買入和賣出的時間點至少需要相差 $k$
最多只能買入和賣出一次，請輸出最大的收益
如果不能夠得到正收益的話，請輸出 $0$

Input

第一行有兩個數字 $n,\ k$

第二行有 $n$ 個數字 $a_i$，代表第 $i$ 個時間點寶石的價錢。

$1 \leq k < n \leq 10^5$

$0\leq a_i \leq 10^9$

有$50\%$的分數滿足$k=1$

Output

輸出一個數字，代表最大的正收益，如果最大收益 <0，則輸出 0

Sample Input #1

5 1
1 4 2 5 4

Sample Output #1

Sample Input #2

5 2
2 100 1 300 7

Sample Output #2

Sample Input #3

6 5
6 5 3 2 4 1

Sample Output #3

測資資訊：

記憶體限制： 64 MB
公開測資點#0 (5%): 1.0s , <1M
公開測資點#1 (5%): 1.0s , <1M
公開測資點#2 (5%): 1.0s , <1M
公開測資點#3 (5%): 1.0s , <1M
公開測資點#4 (5%): 1.0s , <1M
公開測資點#5 (5%): 1.0s , <1M
公開測資點#6 (5%): 1.0s , <1M
公開測資點#7 (5%): 1.0s , <1M
公開測資點#8 (5%): 1.0s , <1M
公開測資點#9 (5%): 1.0s , <1M
公開測資點#10 (5%): 1.0s , <1M
公開測資點#11 (5%): 1.0s , <1M
公開測資點#12 (5%): 1.0s , <1M
公開測資點#13 (5%): 1.0s , <1M
公開測資點#14 (5%): 1.0s , <1M
公開測資點#15 (5%): 1.0s , <1M
公開測資點#16 (5%): 1.0s , <1M
公開測資點#17 (5%): 1.0s , <1M
公開測資點#18 (5%): 1.0s , <1M
公開測資點#19 (5%): 1.0s , <1M

Hint ：

在第三筆範例中，只能在 1 時間買入並在 6 時間賣出，無法得到正收益，因此輸出 $0$

Tags:

出處:

[管理者：

TCIRC ($\mathbb{TCFSH}\ \mathtt{Comp.}\ \&\ \mathsf{Info.}\ \mathit{Club}$)

]

ID	User	Problem	Subject	Hit	Post Date
沒有發現任何「解題報告」